响应式网站模板 食品,工业设计产品设计公司排名,app怎样制作软件,易推客app拉新平台题目链接 描述 思路#xff1a;
递归构造二叉树在Day15有讲到。复习一下#xff0c;就是使用递归构建左右子树。将中序和前序一分为二。 接下来是找出每一层的最右边的节点#xff0c;可以利用队列层次遍历。 利用队列长度记录当前层有多少个节点#xff0c;每次从队列里…题目链接 描述 思路
递归构造二叉树在Day15有讲到。复习一下就是使用递归构建左右子树。将中序和前序一分为二。 接下来是找出每一层的最右边的节点可以利用队列层次遍历。 利用队列长度记录当前层有多少个节点每次从队列里取一个节点就size-1当size为0时即为该层的最后一个节点然后更新size为队列长度。
代码
import queue
def constructTree(preOrder,vinOrder):# 递归退出条件if len(preOrder) 0:return None# 根节点root_val preOrder[0]root TreeNode(root_val)index vinOrder.index(root_val)leftnode constructTree(preOrder[1:index1], vinOrder[:index])rightnode constructTree(preOrder[index1:],vinOrder[index1:])root.left leftnoderoot.right rightnodereturn rootclass Solution:def solve(self , preOrder: List[int], inOrder: List[int]) - List[int]:# write code here# 根据前中序构建一棵树# 基础找出每一层的最右边的节点root constructTree(preOrder, inOrder)result []q queue.Queue()q.put(root)# 记录每一层的sizesize 1while not q.empty():node q.get()if node.left:q.put(node.left)if node.right:q.put(node.right)size - 1if size 0:# 最后一个节点size q.qsize()result.append(node.val)return result 还完债了回家就刀片嗓有点难受啊以后再也不吃啫啫煲了好上火。
