199_二叉树的右视图.org

题目

思路

• (1)BFS: 对二叉树做层序遍历，每一层保存最右侧节点值即可
• (2)DFS: 按照 根->右->左 的顺序访问，就可以保证每层都是最先访问最右边的节点;同时需要更新当前层的树的深度，确保只保存最右侧的节点值

code

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

        if not root: return []

        # (2)DFS 根->右->左 的顺序访问
        res = []
        def helper(root, depth):
            if not root: return
            # 如果当前节点所在深度还没有出现在res里，说明在该深度下当前节点是第一个被访问的节点，因此将当前节点加入res中。
            if depth == len(res):
                res.append(root.val)
            depth += 1
            helper(root.right, depth) # 先右后左
            helper(root.left, depth)
        helper(root, 0)
        return res

        # (1)BFS
        queue = [root]
        res = [root.val]
        while queue:    
            qq = []
            tmp = []
            for node in queue:
                if node.left:
                    qq.append(node.left)
                    tmp.append(node.left.val)
                if node.right:
                    qq.append(node.right)
                    tmp.append(node.right.val)
            if tmp:
                res.append(tmp[-1])
            queue = qq 
        return res