讨论/《深度优先搜索》 - 练习:从中序与后序遍历序列构造二叉/
《深度优先搜索》 - 练习:从中序与后序遍历序列构造二叉
class Solution {

    Map<Integer, Integer> cache = new HashMap<>();

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return buildTree(inorder, 0, inorder.length, postorder, 0, postorder.length);
    }

    public TreeNode buildTree(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {
        if (inStart == inEnd) {
            return null;
        }
        int root =  postorder[postEnd - 1];
        int rootIndexInorder = find(inorder, inStart, inEnd, root);
        int leftCount = rootIndexInorder - inStart;
        TreeNode tree = new TreeNode(root);
        tree.left = buildTree(inorder, inStart, rootIndexInorder, postorder, postStart, postStart + leftCount);
        tree.right = buildTree(inorder, rootIndexInorder + 1, inEnd, postorder, postStart + leftCount, postEnd - 1);
        return tree;
    }

    public int find(int[] flatTree, int start, int end, int target) {
        Integer ret = cache.get(target);
        if (ret != null) {
            return ret;
        }
        for (int i = start; i < end; i++) {
            if (flatTree[i] == target) {
                return i;
            } else {
                cache.put(flatTree[i], i);
            }
        }
        return -1;
    }
}
展开全部 4 讨论