二叉树的右视图 | 秋招知识库

方法一：BFS

套用 102 题的 BFS 模板，把每一层的最后一个节点值保存到答案中。

Python 解法1C++ 解法1

python

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if root is None:
            return []
        ans = []
        cur = [root]
        while cur:
            ans.append(cur[-1].val)
            nxt = []
            for node in cur:
                if node.left:  nxt.append(node.left)
                if node.right: nxt.append(node.right)
            cur = nxt
        return ans

cpp

// C++ 版待补充

C++ 解法2

cpp

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        if (root == nullptr) {
            return {};
        }
        vector<int> ans;
        vector<TreeNode*> cur = {root};
        while (cur.size()) {
            ans.push_back(cur.back()->val);
            vector<TreeNode*> nxt;
            for (auto node : cur) {
                if (node->left)  nxt.push_back(node->left);
                if (node->right) nxt.push_back(node->right);
            }
            cur = move(nxt);
        }
        return ans;
    }
};

注：也可以先把右儿子加入节点数组，这样 $cur [0]$ 就是每层最右边的节点。

复杂度分析

时间复杂度： $O (n)$ ，其中 $n$ 为二叉树的节点个数。虽然写了个二重循环，但每个节点只会添加到列表中一次，所以总的循环次数是节点个数之和，即 $O (n)$ 。
空间复杂度： $O (n)$ 。满二叉树（每一层都填满）最后一层有大约 $n / 2$ 个节点，因此节点数组中最多有 $O (n)$ 个元素，所以空间复杂度是 $O (n)$ 的。

方法二：DFS

视频讲解：【基础算法精讲 10】，欢迎点赞关注~

先递归右子树，再递归左子树，当某个深度首次到达时，对应的节点就在右视图中。

Python 解法3C++ 解法3

python

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        ans = []

        def dfs(node: Optional[TreeNode], depth: int) -> None:
            if node is None:
                return
            if depth == len(ans):  # 这个深度首次遇到
                ans.append(node.val)
            dfs(node.right, depth + 1)  # 先递归右子树，保证首次遇到的一定是最右边的节点
            dfs(node.left, depth + 1)

        dfs(root, 0)
        return ans

cpp

// C++ 版待补充

C++ 解法4

cpp

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> ans;

        auto dfs = [&](this auto&& dfs, TreeNode* node, int depth) -> void {
            if (node == nullptr) {
                return;
            }
            if (depth == ans.size()) { // 这个深度首次遇到
                ans.push_back(node->val);
            }
            dfs(node->right, depth + 1); // 先递归右子树，保证首次遇到的一定是最右边的节点
            dfs(node->left, depth + 1);
        };

        dfs(root, 0);
        return ans;
    }
};

复杂度分析

时间复杂度： $O (n)$ ，其中 $n$ 是二叉树的节点个数。
空间复杂度： $O (h)$ ，其中 $h$ 是二叉树的高度。递归需要 $O (h)$ 的栈空间。最坏情况下，二叉树退化成一条链，递归需要 $O (n)$ 的栈空间。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

方法一：BFS ​

复杂度分析 ​

方法二：DFS ​

复杂度分析 ​

分类题单 ​

方法一：BFS

复杂度分析

方法二：DFS

复杂度分析

分类题单