Day99 | 灵神 | 二叉树 二叉树的右视图

199.二叉树的右视图

199. 二叉树的右视图 - 力扣（LeetCode）

思路：

笔者的思路并不敏捷，所以第一时间只能想到层序遍历，然后把每层的最后一个给放到数组里面去

灵神的思路：

按照根右左的顺序遍历，只要当前结点的深度是第一次遍历到，那必然是最右侧的节点

找左视图的话那肯定就是根左右的顺序遍历了

完整代码：

cpp
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
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> res;   
        if(root==nullptr)
            return res;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty())
        {
            int size=q.size();
            for(int i=0;i<size;i++)
            {
                TreeNode *t=q.front();
                if(i==size-1) 
                    res.push_back(t->val);
                q.pop();
                if(t->left)
                    q.push(t->left);
                if(t->right)
                    q.push(t->right);
            }
        }
        return res;
    }
};

灵神的简洁版代码

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

等价于以下代码

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    vector<int> ans;
    void dfs(TreeNode* node, int depth) {
        if (node == nullptr) {
            return;
        }
        if (depth == ans.size()) { // 这个深度首次遇到
            ans.push_back(node->val);
        }
        cout<<node->val<<endl;
        dfs(node->right, depth + 1); // 先递归右子树，保证首次遇到的一定是最右边的节点
        dfs(node->left, depth + 1);
    }

public:
    vector<int> rightSideView(TreeNode* root) {
        dfs(root, 0);
        return ans;
    }
};