算法题根据前序和后序遍历构造二叉树-编程实验室

根据前序和后序遍历构造二叉树

问题描述

给定前序遍历和后序遍历的结果，构造并返回二叉树。

注意：理论上，仅凭前序和后序遍历无法唯一确定一棵二叉树（缺少中序遍历的根位置信息）。保证：

所有节点值唯一
返回任意一个满足条件的二叉树即可

遍历定义：

前序遍历：根 → 左子树 → 右子树
后序遍历：左子树 → 右子树 → 根

示例：

输入:preorder=[1,2,4,5,3,6,7],postorder=[4,5,2,6,7,3,1]输出:[1,2,3,4,5,6,7]解释:1/\23/\/\4567输入:preorder=[1,2,3],postorder=[3,2,1]输出:[1,2,null,null,3]或[1,null,2,3,null]

算法思路

核心：
- 前序遍历的第一个元素 = 根节点
- 后序遍历的最后一个元素 = 根节点
- 前序遍历的第二个元素 = 左子树的根（如果有左子树）
- 在后序遍历中找到左子树根的位置，可以确定左子树的范围

代码实现

方法一：递归 + 哈希表

importjava.util.*;// 二叉树节点定义classTreeNode{intval;TreeNodeleft;TreeNoderight;TreeNode(){}TreeNode(intval){this.val=val;}TreeNode(intval,TreeNodeleft,TreeNoderight){this.val=val;this.left=left;this.right=right;}}classSolution{/** * 根据前序和后序遍历构造二叉树 * * @param preorder 前序遍历数组 * @param postorder 后序遍历数组 * @return 构造的二叉树根节点 * * 算法思路： * 1. 使用哈希表存储后序遍历中每个值的索引 * 2. 递归分治：根据左子树根确定左右子树范围 * 3. 默认将不确定的子树作为左子树 */publicTreeNodeconstructFromPrePost(int[]preorder,int[]postorder){// 创建哈希表：值 -> 后序遍历中的索引Map<Integer,Integer>postIndexMap=newHashMap<>();for(inti=0;i<postorder.length;i++){postIndexMap.put(postorder[i],i);}returnbuildTree(preorder,0,preorder.length-1,postorder,0,postorder.length-1,postIndexMap);}/** * 递归构建二叉树 * * @param preorder 前序遍历数组 * @param preStart 前序起始索引 * @param preEnd 前序结束索引 * @param postorder 后序遍历数组 * @param postStart 后序起始索引 * @param postEnd 后序结束索引 * @param postIndexMap 后序值到索引的映射 * @return 子树根节点 */privateTreeNodebuildTree(int[]preorder,intpreStart,intpreEnd,int[]postorder,intpostStart,intpostEnd,Map<Integer,Integer>postIndexMap){// 基础情况：空范围if(preStart>preEnd){returnnull;}// 创建根节点TreeNoderoot=newTreeNode(preorder[preStart]);// 基础情况：只有一个节点if(preStart==preEnd){returnroot;}// 找到左子树的根节点（前序的第二个元素）intleftRootVal=preorder[preStart+1];intleftRootPostIndex=postIndexMap.get(leftRootVal);// 计算左子树的节点数量intleftSubtreeSize=leftRootPostIndex-postStart+1;// 递归构建左子树// 左子树前序范围：[preStart+1, preStart+leftSubtreeSize]// 左子树后序范围：[postStart, leftRootPostIndex]root.left=buildTree(preorder,preStart+1,preStart+leftSubtreeSize,postorder,postStart,leftRootPostIndex,postIndexMap);// 递归构建右子树// 右子树前序范围：[preStart+leftSubtreeSize+1, preEnd]// 右子树后序范围：[leftRootPostIndex+1, postEnd-1]root.right=buildTree(preorder,preStart+leftSubtreeSize+1,preEnd,postorder,leftRootPostIndex+1,postEnd-1,postIndexMap);returnroot;}}

方法二：简洁递归

classSolution{/** * 简洁：不使用额外参数 */publicTreeNodeconstructFromPrePost(int[]preorder,int[]postorder){if(preorder.length==0)returnnull;TreeNoderoot=newTreeNode(preorder[0]);if(preorder.length==1)returnroot;// 找到左子树根在后序中的位置intleftRootIndex=0;for(inti=0;i<postorder.length;i++){if(postorder[i]==preorder[1]){leftRootIndex=i;break;}}// 分割数组intleftSize=leftRootIndex+1;int[]preLeft=Arrays.copyOfRange(preorder,1,1+leftSize);int[]preRight=Arrays.copyOfRange(preorder,1+leftSize,preorder.length);int[]postLeft=Arrays.copyOfRange(postorder,0,leftSize);int[]postRight=Arrays.copyOfRange(postorder,leftSize,postorder.length-1);// 递归构建root.left=constructFromPrePost(preLeft,postLeft);root.right=constructFromPrePost(preRight,postRight);returnroot;}}

算法分析

时间复杂度：O(n)
- 每个节点被访问一次
- 哈希表查找为 O(1)
- 总体线性时间
空间复杂度：O(n)
- 哈希表：O(n)
- 递归栈：O(h)，其中 h 是树的高度
- 最坏情况（链状树）：O(n)

算法过程

1：preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]

递归过程：

第一层： - root = 1 - leftRoot = 2, 在postorder中索引 = 2 - leftSize = 2 - 0 + 1 = 3 - 左子树: pre=[2,4,5], post=[4,5,2] - 右子树: pre=[3,6,7], post=[6,7,3] 第二层（左子树）： - root = 2 - leftRoot = 4, 在post中索引 = 0 - leftSize = 0 - 0 + 1 = 1 - 左子树: pre=[4], post=[4] - 右子树: pre=[5], post=[5] 第二层（右子树）： - root = 3 - leftRoot = 6, 在post中索引 = 0 - leftSize = 0 - 0 + 1 = 1 - 左子树: pre=[6], post=[6] - 右子树: pre=[7], post=[7] 叶子节点直接返回

2：preorder = [1,2,3], postorder = [3,2,1]

递归过程：

第一层： - root = 1 - leftRoot = 2, 在postorder中索引 = 1 - leftSize = 1 - 0 + 1 = 2 - 左子树: pre=[2,3], post=[3,2] - 右子树: pre=[], post=[] → null 第二层（左子树）： - root = 2 - leftRoot = 3, 在post中索引 = 0 - leftSize = 0 - 0 + 1 = 1 - 左子树: pre=[3], post=[3] - 右子树: null 结果：1为根，2为左子，3为2的左子 1 / 2 / 3

测试用例

importjava.util.*;publicclassTest{// 前序遍历publicstaticList<Integer>preorderTraversal(TreeNoderoot){List<Integer>result=newArrayList<>();preorderHelper(root,result);returnresult;}privatestaticvoidpreorderHelper(TreeNodenode,List<Integer>result){if(node==null)return;result.add(node.val);preorderHelper(node.left,result);preorderHelper(node.right,result);}// 后序遍历publicstaticList<Integer>postorderTraversal(TreeNoderoot){List<Integer>result=newArrayList<>();postorderHelper(root,result);returnresult;}privatestaticvoidpostorderHelper(TreeNodenode,List<Integer>result){if(node==null)return;postorderHelper(node.left,result);postorderHelper(node.right,result);result.add(node.val);}publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：完整二叉树int[]pre1={1,2,4,5,3,6,7};int[]post1={4,5,2,6,7,3,1};TreeNoderoot1=solution.constructFromPrePost(pre1,post1);System.out.println("Test 1 Preorder: "+preorderTraversal(root1));// [1,2,4,5,3,6,7]System.out.println("Test 1 Postorder: "+postorderTraversal(root1));// [4,5,2,6,7,3,1]// 测试用例2：只有左子树int[]pre2={1,2,3};int[]post2={3,2,1};TreeNoderoot2=solution.constructFromPrePost(pre2,post2);System.out.println("Test 2 Preorder: "+preorderTraversal(root2));// [1,2,3]System.out.println("Test 2 Postorder: "+postorderTraversal(root2));// [3,2,1]// 测试用例3：只有右子树int[]pre3={1,2,3};int[]post3={2,3,1};TreeNoderoot3=solution.constructFromPrePost(pre3,post3);System.out.println("Test 3 Preorder: "+preorderTraversal(root3));// [1,2,3]System.out.println("Test 3 Postorder: "+postorderTraversal(root3));// [2,3,1]// 测试用例4：单个节点int[]pre4={1};int[]post4={1};TreeNoderoot4=solution.constructFromPrePost(pre4,post4);System.out.println("Test 4 Preorder: "+preorderTraversal(root4));// [1]System.out.println("Test 4 Postorder: "+postorderTraversal(root4));// [1]// 测试用例5：两个节点int[]pre5={1,2};int[]post5={2,1};TreeNoderoot5=solution.constructFromPrePost(pre5,post5);System.out.println("Test 5 Preorder: "+preorderTraversal(root5));// [1,2]System.out.println("Test 5 Postorder: "+postorderTraversal(root5));// [2,1]// 测试用例6：复杂树int[]pre6={1,2,4,5,3,6};int[]post6={4,5,2,6,3,1};TreeNoderoot6=solution.constructFromPrePost(pre6,post6);System.out.println("Test 6 Preorder: "+preorderTraversal(root6));// [1,2,4,5,3,6]System.out.println("Test 6 Postorder: "+postorderTraversal(root6));// [4,5,2,6,3,1]// 测试用例7：大数值int[]pre7={100,200,300};int[]post7={300,200,100};TreeNoderoot7=solution.constructFromPrePost(pre7,post7);System.out.println("Test 7 Preorder: "+preorderTraversal(root7));// [100,200,300]System.out.println("Test 7 Postorder: "+postorderTraversal(root7));// [300,200,100]}}