从中序与后序遍历序列构造二叉树

/*
 * 思路：
 * 1. 使用Java Stream API处理数组。
 * 2. 后序遍历的最后一个元素是树的根节点。
 * 3. 根据根节点在中序遍历中的位置，将中序遍历分为左右子树。
 * 4. 递归构造左右子树。
 */
import java.util.stream.IntStream;
 
public class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder == null || postorder == null || inorder.length != postorder.length) {
            return null;
        }
        return buildTree(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
    }
 
    private TreeNode buildTree(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {
        if (inStart > inEnd || postStart > postEnd) {
            return null;
        }
        // 根节点的值是后序遍历的最后一个元素
        int rootVal = postorder[postEnd];
        TreeNode root = new TreeNode(rootVal);
        // 找到根节点在中序遍历中的位置
        int rootIndex = IntStream.range(inStart, inEnd + 1)
                                 .filter(i -> inorder[i] == rootVal)
                                 .findFirst()
                                 .orElse(-1);
        // 递归构造左右子树
        root.left = buildTree(inorder, inStart, rootIndex - 1, postorder, postStart, postStart + rootIndex - inStart - 1);
        root.right = buildTree(inorder, rootIndex + 1, inEnd, postorder, postStart + rootIndex - inStart, postEnd - 1);
        return root;
    }
}