涉及知识点:二叉树操作
给定一棵二叉树,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。
示例:
输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:
1 <---
/ \
2 3 <---
\ \
5 4 <---
右视图,实际上就是二叉树每层的最右边的节点,可以用 层次遍历 来解决。
主要思路就是:
level
来记录当前节点所在的层次。本解法 Python
代码如下
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def rightSideView(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
Q = [] # 队列, 用于层次遍历
level_search = {} # 存储层次遍历的结果,为了方便操作,用字典存储,key是层数,value是该层的元素
if root is not None:
Q.append((root, 0)) # 开始层次遍历,并记录每个节点的层数
while len(Q) > 0:
this_node, level = Q.pop(0)
if level not in level_search:
level_search[level] = []
level_search[level].append(this_node.val) # 把该节点放到对应的层中
if this_node.left is not None:
Q.append((this_node.left, level+1))
if this_node.right is not None:
Q.append((this_node.right, level+1))
res = []
for k in level_search.keys():
res.append(level_search[k][-1]) # 输出每层最后一个节点
return res