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

问题描述

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

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

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

遍历定义：

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

示例：

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

输入: preorder = [1,2,3], postorder = [3,2,1]  
输出: [1,2,null,null,3] 或 [1,null,2,3,null]

算法思路

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

代码实现

方法一：递归 + 哈希表

import java.util.*;

// 二叉树节点定义
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    /**
     * 根据前序和后序遍历构造二叉树
     * 
     * @param preorder 前序遍历数组
     * @param postorder 后序遍历数组
     * @return 构造的二叉树根节点
     * 
     * 算法思路：
     * 1. 使用哈希表存储后序遍历中每个值的索引
     * 2. 递归分治：根据左子树根确定左右子树范围
     * 3. 默认将不确定的子树作为左子树
     */
    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        // 创建哈希表：值 -> 后序遍历中的索引
        Map<Integer, Integer> postIndexMap = new HashMap<>();
        for (int i = 0; i < postorder.length; i++) {
            postIndexMap.put(postorder[i], i);
        }
        
        return buildTree(
            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 子树根节点
     */
    private TreeNode buildTree(
        int[] preorder, int preStart, int preEnd,
        int[] postorder, int postStart, int postEnd,
        Map<Integer, Integer> postIndexMap
    ) {
        // 基础情况：空范围
        if (preStart > preEnd) {
            return null;
        }
        
        // 创建根节点
        TreeNode root = new TreeNode(preorder[preStart]);
        
        // 基础情况：只有一个节点
        if (preStart == preEnd) {
            return root;
        }
        
        // 找到左子树的根节点（前序的第二个元素）
        int leftRootVal = preorder[preStart + 1];
        int leftRootPostIndex = postIndexMap.get(leftRootVal);
        
        // 计算左子树的节点数量
        int leftSubtreeSize = 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
        );
        
        return root;
    }
}

方法二：简洁递归

class Solution {
    /**
     * 简洁：不使用额外参数
     */
    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        if (preorder.length == 0) return null;
        
        TreeNode root = new TreeNode(preorder[0]);
        if (preorder.length == 1) return root;
        
        // 找到左子树根在后序中的位置
        int leftRootIndex = 0;
        for (int i = 0; i < postorder.length; i++) {
            if (postorder[i] == preorder[1]) {
                leftRootIndex = i;
                break;
            }
        }
        
        // 分割数组
        int leftSize = 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);
        
        return root;
    }
}

算法分析

• 时间复杂度：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

测试用例

import java.util.*;

public class Test {
    // 前序遍历
    public static List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        preorderHelper(root, result);
        return result;
    }
    
    private static void preorderHelper(TreeNode node, List<Integer> result) {
        if (node == null) return;
        result.add(node.val);
        preorderHelper(node.left, result);
        preorderHelper(node.right, result);
    }
    
    // 后序遍历
    public static List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        postorderHelper(root, result);
        return result;
    }
    
    private static void postorderHelper(TreeNode node, List<Integer> result) {
        if (node == null) return;
        postorderHelper(node.left, result);
        postorderHelper(node.right, result);
        result.add(node.val);
    }
    
    public static void main(String[] args) {
        Solution solution = new Solution();
        
        // 测试用例1：完整二叉树
        int[] pre1 = {1,2,4,5,3,6,7};
        int[] post1 = {4,5,2,6,7,3,1};
        TreeNode root1 = 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};
        TreeNode root2 = 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};
        TreeNode root3 = 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};
        TreeNode root4 = 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};
        TreeNode root5 = 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};
        TreeNode root6 = 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};
        TreeNode root7 = 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]
    }
}

关键点

1. 索引计算：

   • 左子树大小 = leftRootPostIndex - postStart + 1
   • 右子树后序范围不包含最后一个元素（根节点）

2. 边界条件：

   • 空数组返回 null
   • 单元素数组直接返回节点

3. 哈希表：

   • 避免每次线性搜索后序数组
   • 将时间复杂度从 O(n²) 优化到 O(n)

常见问题

1. 为什么不能唯一确定二叉树？

   • 例如：只有左子树 或 只有右子树，在前序和后序中表现相同
   • 前序：[1,2]，后序：[2,1] 可以是 1->left=2 或 1->right=2

2. 如果需要唯一？

   • 需要中序遍历作为额外信息
   • 前序+中序 或 中序+后序 可以唯一确定二叉树