199. 二叉树的右视图

给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

Solution1（迭代版）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        queue<TreeNode*> q;
        vector<int> res;
        if(!root) return res;
        q.push(root);
        TreeNode* t = NULL;
        while(!q.empty()){
            int len = q.size();
            while(len){
                t = q.front();q.pop();
                if(t->left) q.push(t->left);
                if(t->right) q.push(t->right);
                len--;
            }
            res.push_back(t->val);
        }
        return res;
    }
};

第一种比较符合直觉的就是使用层序遍历，将每一层的最后一个留下。

Solution2（递归版）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> res;
        preorder(root, 1, res);
        return res;
    }
    
    void preorder(TreeNode* node, int depth, vector<int> & res){
        if(!node) return;
        if(res.size() < depth){
            res.push_back(node->val);
        }else{
            res[depth-1] = node->val;
        }
        preorder(node->left,depth+1, res);
        preorder(node->right,depth+1, res);
    }
};

使用前序遍历，并且传入层级信息，每到一层，就将该层的信息更新。如果该层没有数据，则新增一层。遍历到最后就会更新为正确的数据。

优化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> res;
        preorder(root, 0, res);
        return res;
    }
    
    void preorder(TreeNode* node, int depth, vector<int> & res){
        if(!node) return;
        if(res.size() == depth){
            res.push_back(node->val);
        }
        preorder(node->right,depth+1, res);
        preorder(node->left,depth+1, res);
    }
};

思路：

仔细观察发现，并没有必要先push进去左节点，碰到右节点再将左节点覆盖掉，而是一开始就直接push进右节点。到左节点的时候就什么事情也不需要做。

每到一个结点优先遍历右节点，res的size++。在遍历左节点的时候直接会跳过。