?LeetCode刷題實戰(zhàn)199：二叉樹的右視圖
Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
題意
示例
解題
思路一：廣度優(yōu)化搜索
class Solution:
def rightSideView(self, root: TreeNode) -> List[int]:
if root == None:
return []
# 導入 deque 創(chuàng)建隊列
from collections import deque
queue = deque([root])
res = []
while queue:
size = len(queue)
# 這里用 size 記錄二叉樹每層的節(jié)點數(shù)，
for i in range(size):
# 彈出節(jié)點
node = queue.popleft()
# 先將左節(jié)點入隊
if node.left != None:
queue.append(node.left)
# 再將右節(jié)點入隊
if node.right != None:
queue.append(node.right)
# 隊列先入先出，如果 i 等于 size - 1，
# 那么這里就是最右邊的節(jié)點，這個就要得到的結(jié)果，將其放入返回列表中
if i == size - 1:
res.append(node.val)
return res
思路二：深度優(yōu)化搜索
class Solution:
def rightSideView(self, root: TreeNode) -> List[int]:
res = []
def _dfs(node, depth):
if node == None:
return []
# res 的索引表示二叉樹的深度
# 若當前的深度的節(jié)點不存在于 res 中，
# 表示該層的最右邊節(jié)點還未將其添加到 res 中
# 將其加入到節(jié)點中
if depth == len(res):
res.append(node.val)
# 往一下層訪問，先訪問右子樹，在訪問左子樹
depth += 1
_dfs(node.right, depth)
_dfs(node.left, depth)
_dfs(root, 0)
return res