题目

https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

题解

待优化：可以用 map 存一下每一个前序遍历元素对应的下标，这样更快一些。

/** * Definition for a binary tree node. * public 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 {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return process(inorder, postorder, 0, inorder.length - 1, 0, postorder.length - 1);
    }

    public TreeNode process(int[] inorder, int[] postorder, int L1, int R1, int L2, int R2) {
        if (L1 > R1) return null;
        TreeNode root = new TreeNode(postorder[R2]);
        for (int M1 = L1, n = 0; M1 <= R1; M1++, n++) {
            if (inorder[M1] == postorder[R2]) {
                root.left = process(inorder, postorder, L1, M1 - 1, L2, L2 + n - 1);
                root.right = process(inorder, postorder, M1 + 1, R1, L2 + n, R2 - 1);
                return root;
            }
        }
        return root;
    }
}