二叉树的右序图

给定一棵二叉树,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。

示例:

输入: [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

解决该题的方法是用深度优先的遍历,进行层遍历,每次遍历记录下最先遍历到的数值,因为每次都是从右边遍历的,所以得到的列表值就是答案,以下代码来自官方题解:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def rightSideView(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)]

字典中的一个方法 setdefault(key, value), 该方法只会在没有该键的时候插入,若存在则不插入。

点赞

发表评论

Title - Artist
0:00