按层遍历,旧一层的队列直接被新一层替换,简单粗暴,也省得出队了,跟我上一篇思路几乎一样,就这点不同
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
# 求二叉树的右视图
# @param xianxu int整型一维数组 先序遍历
# @param zhongxu int整型一维数组 中序遍历
# @return int整型一维数组
#
class TreeNode:
def __init__(self, val, left = None, right = None):
self.val = val
self.left = left
self.right = right
class Solution:
def build(self, x, z):
if not x or not z:
return None
root = TreeNode(x[0])
index = z.index(x[0])
root.left = self.build(x[1:index + 1], z[:index])
root.right = self.build(x[index + 1:], z[index + 1:])
return root
def solve(self , xianxu , zhongxu ):
# write code here
root = self.build(xianxu, zhongxu)
if not root:
return []
queue = [root]
res = []
while queue:
next_list, vals = [], [] #每次都清零
for node in queue: #遍历一层的元素
if node.left:
next_list.append(node.left)
if node.right:
next_list.append(node.right)
vals.append(node.val)
queue = next_list #旧一层的队列直接被新一层替换,简单粗暴,也省得出队了
if vals:
res.append(vals[-1]) #提取每层的最后一个
return res