算法

(DFS) $O(nlog(n))$

1. 后序遍历的最后一个节点一定是当前树的根节点，即left subtree root
2. 在中序遍历中搜索得到该节点，则其左侧序列为该根节点的左子树，右侧序列为该节点的右子树，即left subtree right subtree
3. 因为左右子树在中序、后序遍历中的序列长度必定一样，所以可以通过中序遍历中root的index位置计算出后序序列中左、右子树的切片序列
4. 递归重复该过程

C++ 代码

class Solution {
public:
    typedef vector<int>::iterator Iter;
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (inorder.size() == 0)
            return NULL;
        return buildTreeRecur(inorder.begin(), inorder.end(), postorder.begin(), 
        postorder.end());
    }

    TreeNode *buildTreeRecur(Iter istart, Iter iend, Iter pstart, Iter pend){
        if(istart == iend)return NULL;

        int rootval = *(pend-1);
        Iter iterroot = find(istart, iend, rootval);
        TreeNode *res = new TreeNode(rootval);

        res->left = buildTreeRecur(istart, iterroot, pstart, pstart+(iterroot-istart));
        res->right = buildTreeRecur(iterroot+1, iend, pstart+(iterroot-istart), pend-1);
        return res;
    }
};

Java 代码

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return build(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
    }

    private TreeNode build(int[] in, int istart, int iend, int[] po, int pstart, int pend) {
        if (pstart > pend) return null;

        TreeNode root = new TreeNode(po[pend]); 

        int idx = findPos(in, istart, iend, po[pend]); // 获取root在inorder中的位置
        int rlen = iend - idx;
        int llen = idx - istart;

        TreeNode right = build(in, idx + 1, iend, po, pend - rlen, pend - 1);
        TreeNode left = build(in, istart, idx - 1, po, pstart, pstart + llen - 1);

        root.left = left;
        root.right = right;
        return root;
    }

    private int findPos(int[] a, int start, int end, int target) {
        int res = -1;
        for (int i = start; i <= end; ++i) {
            if (a[i] == target) return i;
        }
        return -1;
    }
}