按层遍历,旧一层的队列直接被新一层替换,简单粗暴,也省得出队了,跟我上一篇思路几乎一样,就这点不同

#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
# 求二叉树的右视图
# @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