国内10大网站建设公司,企业工商公示信息查询系统,企业做网站天津,任丘做网站题目#xff1a; 给定两个整数数组 preorder 和 inorder #xff0c;其中 preorder 是二叉树的先序遍历#xff0c; inorder 是同一棵树的中序遍历#xff0c;请构造二叉树并返回其根节点。 来源#xff1a;力扣#xff08;LeetCode#xff09; 链接#xff1a;力扣 给定两个整数数组 preorder 和 inorder 其中 preorder 是二叉树的先序遍历 inorder 是同一棵树的中序遍历请构造二叉树并返回其根节点。 来源力扣LeetCode 链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台 示例 示例 1 输入preorder [3,9,20,15,7], inorder [9,3,15,20,7] 输出[3,9,20,null,null,15,7] 示例 2 输入preorder [-1], inorder [-1] 输出[-1] 解法 使用栈辅助stack栈中每个结点结构为[当前结点在中序序列中的下标, 树节点]stack初始化的值是前序序列第0个。用栈的目的是当插入结点为右子树时确定其根节点。 遍历前序序列 从第1个开始。获取当前值在中序序列中的下标如果比stack中最后1个小说明当前结点是前个结点的左子树否则需要弹出栈顶直到比stack中最后1个大此时说明当前结点在弹出结点的右边在栈最后1个结点的左边所以把当前结点接到弹出结点的右子树。 知识点 1.前序遍历根-左-右。 代码 # Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution:def buildTree(self, preorder: List[int], inorder: List[int]) - Optional[TreeNode]:root tree TreeNode(preorder[0])stack [[inorder.index(preorder[0]), tree]]for num in preorder[1:]:index inorder.index(num)tree TreeNode(num)if index stack[-1][0]:stack[-1][1].left treeelse:while stack and index stack[-1][0]:pre stack.pop()pre[1].right treestack.append([index, tree])return root
