mq041.二叉树的右视图

题目链接

对于这个题有两种思路，我之前的想法是宽度优先遍历既层序遍历二叉树，每一层的最后一个节点就是所求的值，但是有一种更省空间的方法就是记录下每个节点的深度并且用深度作为键节点的值作为值建立字典并同时更新，因为最右边的节点最后才会遍历到所以字典里最后保存的会是最右边的节点的值（如1）。另外一种思路用深度优先遍历并且先遍历右子节点（如2），这样做的结果就是对于某个深度的最开始遇到的节点才是需要记录的值。这两个算法的时间复杂度都是O（N），空间复杂度都是O（N）。

class Solution:
    def rightSideView1(self, root: TreeNode) -> List[int]:
        most_right = {}
        max_depth = -1
        queue = [(root, 0)]
        while queue:
            node, depth = queue.pop(0)

            if node:
                max_depth = max(max_depth, depth)
                most_right[depth] = node.val
                queue.append((node.left, depth+1))
                queue.append((node.right, depth+1))
        return [most_right[x] for x in range(max_depth+1)]

    def rightSideView2(self, root):
        rightmost_value_at_depth = dict() # 深度为索引，存放节点的值
        max_depth = -1

        stack = [(root, 0)]
        while stack:
            node, depth = stack.pop()

            if node is not None:
                # 维护二叉树的最大深度
                max_depth = max(max_depth, depth)

                # 如果不存在对应深度的节点我们才插入
                rightmost_value_at_depth.setdefault(depth, node.val)

                stack.append((node.left, depth+1))
                stack.append((node.right, depth+1))

        return [rightmost_value_at_depth[depth] for depth in range(max_depth+1)]

PREVIOUSlc199.二叉树的右视图

NEXTpp001.模版