每天学习一点算法 2026/03/11题目从前序与中序遍历序列构造二叉树给定两个整数数组 preorder 和 inorder 其中 preorder 是二叉树的先序遍历 inorder 是同一棵树的中序遍历请构造二叉树并返回其根节点。我们知道先序遍历的遍历顺序是根节点→左子节点→右子节点中序遍历的遍历顺序是左子节点→根节点→右子节点。我们以preorder [3,9,20,15,7], inorder [9,3,15,20,7]为例首先可以得到preorder的第一项3是总的根节点然后我们在inorder中找到3 那么3左边的部分[9]就是左子树3右边的部分[15,20,7]就是右子树因为左子树有内容我们将preorder的第二项9就是3节点的左子节点3 / 9然后9作为根节点[9]中找到9左右都没有元素了所以他就是叶子结点了然后preorder第三项20就是3的右节点3 / \ 9 20然后20作为根节点[15,20,7]中找到20分为左边部分[15]和 右边部分[7]后面也就按这个步骤一直分割就行这样就可以得到树结构3 / \ 9 20 / \ 15 7我们可以看到我们需要做的是遍历先序的数组然后不断分割中序数组最容易想到的就是递归/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) { * this.val (valundefined ? 0 : val) * this.left (leftundefined ? null : left) * this.right (rightundefined ? null : right) * } * } */functionbuildTree(preorder:number[],inorder:number[]):TreeNode|null{letindex0// preorder 指针returnhelper(inorder)// 调用辅助函数递归生成树functionhelper(arr:number[]){if(arr.length0)returnnull// 分割结果为空是返回nullconstnodenewTreeNode(preorder[index])// 根据当前指针创建当前根节点constiarr.findIndex(valpreorder[index]val)// 找到根节点在 arr 中位置if(i0){// 存在左树数据indexnode.lefthelper(arr.slice(0,i))}if(iarr.length-1){// 存在右树数据indexnode.righthelper(arr.slice(i1))}returnnode// 返回当前根节点}};还有一个迭代的方法有点复杂我们直接用一个例子来讲3 / \ 9 20 / / \ 8 15 7 / \ 5 10 / 4preorder [3, 9, 8, 5, 4, 10, 20, 15, 7] inorder [4, 5, 8, 10, 9, 3, 15, 20, 7]我们观察一下preorder[i]和preorder[i 1]有两种情况preorder[i 1]是preorder[i]的左子结点preorder[i]没有左子节点preorder[i 1]是preorder[i]某一个父节点的 右子节点根据这个规律我们可以维护一个栈存放判断右节点的节点通过遍历preorder来还原树结构具体步骤如下首先定义一个指针指向inorder的第一个元素4接着我们开始遍历preorder首先是3首位直接入栈然后遍历到9关键点来了我们如何判断这个9是不是3的左节点呢假设不是的话3是不是就应该是最左侧的节点但是我们目前还没做任何操作最左侧的节点应该是4所以我们可以确定9是3的左子结点我们将3左侧指向节点9并将节点9入栈。然后8, 5, 4一样的操作等到10时我们可以发现 上一个节点4就是当前最左侧的节点那么10就是节点4的某个父节点我们怎么寻找这个父节点呢我们可以看到只有左节点的树前序遍历的结果就是中序遍历结果的反转那么移动的指针并弹栈弹栈节点和指针指向值相等时就是我们要找的父节点8我们将8右侧指向节点9并将节点9入栈。就这样遍历完所有的preorder元素就可以还原整个树了function buildTree(preorder: number[], inorder: number[]): TreeNode | null { if (preorder.length 0) return null const stack: TreeNode[] [] const root new TreeNode(preorder[0]) stack.push(root) let index 0 for (let i 1; i preorder.length; i) { let node stack[stack.length - 1] if (inorder[index] ! node.val) { node.left new TreeNode(preorder[i]) stack.push(node.left) } else { while (stack.length 0 stack[stack.length - 1].val inorder[index]) { index node stack.pop() } node.right new TreeNode(preorder[i]) stack.push(node.right) } } return root };题目来源力扣LeetCode