LeetCode 第 199 题:“二叉树的右视图”题解

题解地址:DFS 和 BFS(Python 代码)

说明:文本首发在力扣的题解版块,更新也会在第 1 时间在上面的网站中更新,这篇文章只是上面的文章的一个快照,您可以点击上面的链接看到其他网友对本文的评论。

传送门:199. 二叉树的右视图

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

示例:

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

1 <--- /
2 3 <--- \
5 4 <---

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/binary-tree-right-side-view 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

DFS 和 BFS(Python 代码)

方法一:DFS

实际上就是改良了“前序遍历”,“前序遍历”是“先自己,再左子树(如果有的话),再右子树(如果有的话)”。

而我们改过以后是:“先自己,再右子树(如果有的话),再左子树(如果有的话)”。

Python 代码:

from typing import List


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        def dfs(node, res, depth):
            if node is None:
                return
            if len(res) == depth:
                res.append(node.val)
            dfs(node.right, res, depth + 1)
            dfs(node.left, res, depth + 1)

        res = []
        dfs(root, res, 0)
        return res

方法二:BFS

使用层序遍历的思想完成本题思路不难想到,关键是在细节。自己根据题目中的示例,或者你出错的那个测试用例,就很容易看出问题在哪里。

Python 代码:

from typing import List


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        if root is None:
            return []

        res = []
        queue = [root]
        while queue:
            cur_size = len(queue)
            res.append(queue[-1].val)
            # 这里要注意,上一层的结点要全部出列
            for _ in range(cur_size):
                top = queue.pop(0)
                if top.left:
                    queue.append(top.left)
                if top.right:
                    queue.append(top.right)
        return res