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