45 二叉树的右视图

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

提示:

• 二叉树的节点个数的范围是 [0,100]
• -100 <= Node.val <= 100

题解1 层序遍历——BFS

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
         if(!root)  return vector<int>();
        vector<int> res;
        queue<TreeNode*> que;
        que.push(root);
        while(que.size()){
            int s = que.size();
            while(s--){
                auto k = que.front();
                que.pop();
                if(0 == s)
                    res.emplace_back(k->val);
                if(k->left) que.push(k->left);
                if(k->right) que.push(k->right);
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

题解2 递归——DFS

class Solution {
    vector<int> res;
public:
    void dfs(TreeNode* root, int depth){
        if(! root) return;
        // keypoint： 用层数决定是否可以添加左子树的值
        if (res.size() == depth)
            res.emplace_back(root->val);
        if(root->right)
            dfs(root->right, depth+1);
        
        if(root->left)
            dfs(root->left, depth+1);
        
        
    }
    vector<int> rightSideView(TreeNode* root) {
        if(!root)  return vector<int>();
        dfs(root, 0);
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22