199. Binary Tree Right Side View

Loading...LeetCode

DFS 先把最右边的那些node加进去，然后再依序往左边找，确保遍历所有level

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def dfs(self, root, result, level):
        if not root: return
        # 确保只有新到的level会加值进result里面
        if level == len(result): result.append(root.val)
        # 先traverse右边，确保右子树的都加进去
        self.dfs(root.right, result, level+1)
        # 再左边，寻找遗漏的
        self.dfs(root.left, result, level+1)
    
    def rightSideView(self, root: TreeNode) -> List[int]:
        res = []
        self.dfs(root, res, 0)
        return res

既然是二叉树层序遍历，也可以 BFS 做，用 queue，每层都先把当层node的子节点加进queue里面，（这题需要把最右侧node记录下来），下一轮再把queue里的节点进行同样的操作。

class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
    
        res, queue = [], []
        if not root: return res
        queue.append(root)
        
        while queue:
            level = len(queue)
            # 
            res.append(queue[-1].val)
            for i in range(level):
                curNode = queue.pop(0)
                if curNode.left: queue.append(curNode.left)
                if curNode.right: queue.append(curNode.right)
        return res