【数据结构与算法笔记01】对树的遍历过程中的层次追踪方法的思考

1. 题目描述

2. 题目解答

2.1 题目理解：

　　所谓二叉树的右视图就是：每一层只能看到这一层最右边的节点。

2.2 基本思路：

　　（1）深度优先遍历：按照每次先访问右孩子的方式进行深度优先遍历。那么每一层访问到的第一个节点就是该层最右边的节点。

　　（2）广度优先遍历：按照每一层从左向右的方式进行广度优先遍历。那么每一层访问到的最后一个节点就是该层最右边的节点。

2.3 算法细节讨论：

　　（1）结果的存储①：对于每一层的最右边的节点用一个二元组来存储。

　　（2）更新策略：

深度优先遍历：因为每一层只要访问到的第一个节点，所以：每拿到一个第i层的节点node，去看结果集中是否已经有key=i的二元组，如果有就说明该层最右侧的节点已经找到了，如果没有就将data>存入结果集中。
广度优先遍历：因为每一层要的是访问到的最后一个节点，所以：每拿到一个第i层的节点node，就将结果集中key=i的二元组的value更新为node->data。

　　（3）结果的存储②：

　　考虑不同的更新策略得出以下结论：

　　　　1. 最终的结果集中，key值是从1到树深的间隔为1的等差数列（1, 2, 3, ...）。

　　　　2. 最终结果集中的二元组是按照key值从小到大的顺序依次计算出来的。

　　　　3. 在深度优先遍历中，需要知道哪些层的结果已经计算出来了。

　　最终方案：数组

　　1. 因为最终的结果集中key值是从1到树深的间隔为1的等差数列（1, 2, 3, ...），所以可以用数组来存储结果：用数组下标表示depth即可。

　　2. 如果提前知道树深，就可以知道数组的大小，初始化时数组的大小设为树深即可。但是如果提前不知道树深，初始化时数组的大小就应该设为树中结点的个数（要考虑到可能存在每一层只有一个结点的极端情况）。要是连树中结点的个数都不知道，就得要先设一个比较大的值，比如100,1000，这样如果树小的话会浪费空间，如果树大的话又可能要涉及到数组扩容的问题，处理起来比较复杂。

　　3. 在深度优先遍历中存在一个 “去看结果集中是否已经有key=i的二元组” 的操作，因为最终结果集中的二元组是按照key值从小到大的顺序依次计算出来的，所以只要记录当前结果集中已经计算出的最深的二元组是哪一层(max_depth)，就可以认为key<=max_depth的层都已经计算出结果了，key>max_depth的层是尚未计算出结果的层。

　　（4）层次追踪：无论是用DFS还是用BFS，都需要在访问到每一个结点的时候知道该节点在哪一层。

　　如果知道父节点的层次，就能知道子节点的层次。只凭子节点自己是不能知道自己的层次的。也就是说，当前节点究竟在哪一层，这个信息获取的时机是在访问它的父节点的时候。那么关键问题就在于：父节点要如何将这一信息传递给自己的子节点呢？

递归实现：可以在递归调用的时候将这个信息通过参数传递给孩子节点。

　　　　定义：rightViewNode(BiThrNode* node, int depth)

　　　　递归调用：rightViewNode(curNode->lchild, curDepth + 1)

非递归实现：在DFS中使用一个depthStack和nodeStack同步追踪节点的层次；在BFS中使用一个depthQueue和nodeQueue同步追踪节点的层次。

2.4 一些思考

（1）遍历方向：之前似乎有一种错误的想法，认为似乎广度优先遍历只能从左到右，深度优先遍历只能每次优先访问左孩子。但其实广度优先也好，深度优先也好，从来都没有规定过方向，重要的是“广度优先”和“深度优先”这两种思想，具体的访问顺序完全可以根据情况来选择。

（2）为什么这道题广度优先遍历和深度优先遍历都可以？

　　这个问题其实更好的表述方式应该是“为什么深度优先遍历也可以？”，因为这个题目大多数人一看到就会觉得，这就是用广度优先遍历嘛（including me）。

　　其实深入思考一下，所谓的左视图，右视图，只不过是在遍历树的时候的一种访问策略（满足什么条件的时候或者说什么时机对当前节点进行操作），那么既然是遍历，肯定两种方法都是可行的。在深度优先遍历中，这个访问策略是说：如果这个节点是这一层的第一个，那我就对它进行操作。在广度优先遍历中，这个访问策略是说：如果这个节点是这一层最右边的，那我就对它进行操作。

　　所以，这样么想的话，其实对于很多问题如果能认识到它是一个遍历树+访问策略的问题，那么就只需要对每一种遍历方式选择一个合适的访问策略，算法的基本思路就有了。

（3）层次追踪：这道题给我的第三个收获就是如何进行层次追踪，具体内容在前面的文章里。

（4）其他思路：

　　其实在没有刷过任何题的情况下，拿到这道题的时候，我想出来的是另外一种方法，我觉得也还行其实所以记录一下。

　　首先就像前面说的，我一看到这个题我就想到，这不就是广度优先遍历，把每一层最后一个节点打印出来就完事了呗。

　　然后我就想到在学习广度优先遍历（层次遍历）的实现时，我观察到的一个特点：

　　也就是说queue中一开始只有第1层的元素，根据第1层的元素放入了第2层，根据第2层的元素放入了第3层，...，以此类推。

　　但是问题在于，我怎么样才能知道这个节点是这一层的最后一个呢?

　　当时我其实也想到了在用一个队列同步记录每个节点的层次，但是我当时没有考虑将所有的结果存下来，而是希望在访问到这个节点的时候就能够知道这就是最后一个节点，我可以直接print了。这其实有很大的区别，是否需要额外的空间不说。在前面的几种方法中，是不可能在访问到这个节点的时候就能够知道这就是这一层中我要的节点，而是只有到一个走完一遍操作的全局视角的时候，才能知道留在结果集中的那些是需要的节点。

　　所以我采用了另外一种方法，我觉得既然根据第1层的元素放入了第2层，那我为什么非要把第2层都放到同一个队列中呢，就是因为都放在一起了所以才无法区分层次之间的界限呀。因此，我想到用两个队列，Q1和Q2，用他们俩轮流倒着放，这样不就能把每一层区分开了吗？

　　还有一点就是，比如说根据第i层放第i+1层的节点的时候，也就是访问第i层元素的时候。因为是把第i层的节点从第一个队列中一个一个取出来，然后再把他们的左右孩子依次放入另一个队列中。所以我在从第一个队列中取时候，每次判断一下取出来之前队列中还有几个元素就能知道这是不是这一层的最后一个元素了。

　　而且虽然用了两个队列，因为在某一个时间截面来看：这两个队列中元素的个数和之前的一个大队列中元素的个数是一样的，所以其实并没有增加额外的空间。而且相比于之前的几种方法，还能节省一个result数组的空间。至于时间复杂度我觉得都一样，大家都是遍历嘛。

2.5 代码

　　在实现的时候我稍稍投了一下懒，没有用数组存，而是用了map。另外因为之前在看线索树，所以我的代码是在线索树里面写的，会有一些不太一样的操作。

　　额，也就是以下代码仅供参考...

　　1. 两个队列：

template
void BiThrTree::printRightView() {
    queue*> Q1, Q2;
    Q1.push(root); 
    while (!Q1.empty() || !Q2.empty()) {
        pushChildren(Q1, Q2);
        pushChildren(Q2, Q1);
    }
}

template
void BiThrTree::pushChildren(queue*> &fromQ, queue*> &toQ) {
    while (!fromQ.empty()) {
        BiThrNode* curNode = fromQ.front();
        if (fromQ.size() == 1)
            cout << curNode->data << " ";
        fromQ.pop();
        if (curNode->Ltag == 0)
            toQ.push(curNode->lchild);
        if (curNode->Rtag == 0)
            toQ.push(curNode->rchild);
    }
}

　　2. 深度优先遍历（递归）

template
void BiThrTree::rightViewDFSRecursive() {

    rightViewNode(root, 1);

    //printout
    typename map<int, T>::iterator it = rightView.begin();
    while (it != rightView.end()) {
        cout << it->second << " ";
        it++;
    }
}

template
void BiThrTree::rightViewNode(BiThrNode* node, int depth) {
    if (!node) return;

    if (rightView.find(depth) == rightView.end())
        rightView.insert(pair<int, T> (depth, node->data));

    if(node->Rtag == 0)
        rightViewNode(node->rchild, depth + 1);
    if(node->Ltag == 0)
        rightViewNode(node->lchild, depth + 1);
}

　　3. 深度优先遍历（非递归）

template
void BiThrTree::rightViewDFSNonRecur() {
    stack*> nodeStack;
    stack<int> depthStack;

    nodeStack.push(root);
    depthStack.push(1);

    BiThrNode* curNode = nullptr;
    int curDepth = 0;

    while (!nodeStack.empty()) {
        curNode = nodeStack.top();
        nodeStack.pop();
        curDepth = depthStack.top();
        depthStack.pop();

        if (rightView.find(curDepth) == rightView.end())
            rightView.insert(pair<int, T>(curDepth, curNode->data));

        if (curNode->Ltag == 0) {
            nodeStack.push(curNode->lchild);
            depthStack.push(curDepth + 1);
        }

        if (curNode->Rtag == 0) {
            nodeStack.push(curNode->rchild);
            depthStack.push(curDepth + 1);
        }
    }

    //printout
    typename map<int, T>::iterator it = rightView.begin();
    while (it != rightView.end()) {
        cout << it->second << " ";
        it++;
    }
}

　　4.广度优先遍历

template
void BiThrTree::rightViewBFSNonRecur() {
    queue*> nodeQueue;
    queue<int> depthQueue;

    //init
    nodeQueue.push(root);
    depthQueue.push(1);

    BiThrNode* curNode = nullptr;
    int curDepth = 0;

    while (!nodeQueue.empty()) {
        curNode = nodeQueue.front();
        nodeQueue.pop();
        curDepth = depthQueue.front();
        depthQueue.pop();

        rightView[curDepth] = curNode->data;

        if (curNode->Ltag == 0) {
            nodeQueue.push(curNode->lchild);
            depthQueue.push(curDepth + 1);
        }

        if (curNode->Rtag == 0) {
            nodeQueue.push(curNode->rchild);
            depthQueue.push(curDepth + 1);
        }

    }

    //printout
    typename map<int, T>::iterator it = rightView.begin();
    while (it != rightView.end()) {
        cout << it->second << " ";
        it++;
    }
}

总结：

层次追踪的三种方法：

递归实现：可以在递归调用的时候将这个信息通过参数传递给孩子节点。