解题思路

1. 基本原理

  • 后序遍历：左子树 -> 右子树 -> 根节点
  • 中序遍历：左子树 -> 根节点 -> 右子树
  • 关键点：后序遍历的最后一个元素一定是根节点

2. 解题步骤

以输入 [2,1,4,3,5]（中序）和 [2,4,5,3,1]（后序）为例：

  1. 找到根节点：

    • 后序遍历的最后一个元素1是根节点

  2. 在中序遍历中定位根节点：

    • 中序：[2, (1), 4,3,5]
    • 1的位置将中序序列分成左右子树

  3. 划分子树：

    • 左子树：中序 [2]，后序 [2]
    • 右子树：中序 [4,3,5]，后序 [4,5,3]

  4. 递归构建：

    • 对左右子树重复上述过程
    • 左子树：只有一个节点2
    • 右子树：根节点是3，继续划分

3. 图解过程

初始序列：
中序：[2,1,4,3,5]
后序：[2,4,5,3,1]

第一层：
根节点：1
左子树：[2]
右子树：[4,3,5]

构造结果：
     1
    / \
   2   3
      / \
     4   5

4. 注意事项

  1. 确保输入序列长度相等
  2. 处理空树的情况
  3. 注意数组边界
  4. 保存根节点在中序遍历中的位置可以用哈希表优化

代码

class Solution {
private:
    unordered_map<int, int> map;  // 存储中序遍历中值到索引的映射
    vector<int> post;             // 存储后序遍历数组
    
    TreeNode* build(int inStart, int inEnd, int postStart, int postEnd) {
        // 递归终止条件
        if (inStart > inEnd || postStart > postEnd) {
            return nullptr;
        }
        
        // 创建根节点（后序遍历的最后一个元素）
        TreeNode* root = new TreeNode(post[postEnd]);
        
        // 在中序遍历中找到根节点的位置
        int rootIndex = map[root->val];
        
        // 计算左子树的节点个数
        int leftSize = rootIndex - inStart;
        
        // 递归构建左右子树
        root->left = build(inStart, rootIndex - 1, postStart, postStart + leftSize - 1);
        root->right = build(rootIndex + 1, inEnd, postStart + leftSize, postEnd - 1);
        
        return root;
    }
    
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        // 保存后序遍历数组
        post = postorder;
        
        // 构建中序遍历的值到索引的映射
        for (int i = 0; i < inorder.size(); i++) {
            map[inorder[i]] = i;
        }
        
        // 调用递归函数构建树
        return build(0, inorder.size() - 1, 0, postorder.size() - 1);
    }
};

import java.util.*;

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private Map<Integer, Integer> map = new HashMap<>();  // 存储中序遍历中值到索引的映射
    private int[] post;  // 存储后序遍历数组
    
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        post = postorder;
        
        // 构建中序遍历的值到索引的映射
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        
        // 调用递归函数构建树
        return build(0, inorder.length - 1, 0, postorder.length - 1);
    }
    
    private TreeNode build(int inStart, int inEnd, int postStart, int postEnd) {
        // 递归终止条件
        if (inStart > inEnd || postStart > postEnd) {
            return null;
        }
        
        // 创建根节点（后序遍历的最后一个元素）
        TreeNode root = new TreeNode(post[postEnd]);
        
        // 在中序遍历中找到根节点的位置
        int rootIndex = map.get(root.val);
        
        // 计算左子树的节点个数
        int leftSize = rootIndex - inStart;
        
        // 递归构建左右子树
        root.left = build(inStart, rootIndex - 1, postStart, postStart + leftSize - 1);
        root.right = build(rootIndex + 1, inEnd, postStart + leftSize, postEnd - 1);
        
        return root;
    }
}

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        # 创建中序遍历的值到索引的映射
        index_map = {val: i for i, val in enumerate(inorder)}
        
        def build(in_start: int, in_end: int, post_start: int, post_end: int) -> TreeNode:
            # 递归终止条件
            if in_start > in_end or post_start > post_end:
                return None
            
            # 创建根节点（后序遍历的最后一个元素）
            root_val = postorder[post_end]
            root = TreeNode(root_val)
            
            # 在中序遍历中找到根节点的位置
            root_index = index_map[root_val]
            
            # 计算左子树的节点个数
            left_size = root_index - in_start
            
            # 递归构建左右子树
            root.left = build(in_start, root_index - 1, 
                            post_start, post_start + left_size - 1)
            root.right = build(root_index + 1, in_end, 
                             post_start + left_size, post_end - 1)
            
            return root
        
        return build(0, len(inorder) - 1, 0, len(postorder) - 1)

算法及复杂度分析

  • 算法:递归，树的遍历
  • 时间复杂度：，每个节点都需要处理一次
  • 空间复杂度：，需要存储哈希表和递归调用栈

优化方案

  1. 使用哈希表存储中序遍历中节点值与下标的映射，避免重复查找
  2. 使用数组下标而不是切片，减少空间使用
  3. 可以传递边界索引而不是创建新的子数