199_二叉树的右视图

发表于 分类于 ， 阅读次数： Waline： 本文字数： 1.6k 阅读时长 ≈ 1 分钟

199. 二叉树的右视图

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

示例：

输入: [1,2,3,null,5,null,4] 输出: [1,3,4]

输入: [] 输出: []

思路：

方法一：BFS

每次把当前层最后一个结点输出即可 时间复杂度：O(n) 空间复杂度：O(n)

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
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        if(root == nullptr) return {};
        queue<TreeNode*> q;
        vector<int> res;
        q.push(root);

        while(!q.empty()){
            int sz = q.size();
            for(int i = 0; i < sz; i++) {
                TreeNode* cur = q.front();
                q.pop();
                if(i == sz - 1) {
                    res.push_back(cur->val);
                }
                if(cur->left != nullptr) {
                    q.push(cur->left);
                }
                if(cur->right != nullptr) {
                    q.push(cur->right);
                }
            }
        }
        return res;
    }
};

方法二：DFS

反过来的DFS,先遍历右子树再遍历左子树 每层添加一个元素 时间复杂度：O(n) 空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> res;
    int depth = 0;
    vector<int> rightSideView(TreeNode* root) {
        if(root == nullptr) return {};
        dfs(root);
        return res;
    }
    void dfs(TreeNode* root) {
        if(root == nullptr)
            return;
        depth++;
        if(res.size() < depth){
            // 每层增加一个
            res.push_back(root->val);
        }
        dfs(root->right);
        dfs(root->left);
        depth--;
    }
};