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

解法一：递归

后序遍历序列末尾存储根结点，找出其在中序遍历中的位置，即可从源遍历序列中划分出左右子树的范围，递归建树。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return build(inorder, 0, inorder.length, postorder, 0, postorder.length);
    }
    private TreeNode build(final int[] inorder, int inBegin, int inEnd, final int[] postorder, int postBegin, int postEnd) {
        if ((inBegin >= inEnd) || (postBegin >= postEnd)) {
            return null;
        }
        // 后序遍历数组末尾为根结点
        int val = postorder[postEnd - 1];
        TreeNode root = new TreeNode(val);
        // 寻找中序遍历数组中根结点的位置
        int rootIndex = 0;
        for (int i = inBegin; i < inEnd; ++i) {
            if (inorder[i] == val) {
                rootIndex = i;
                break;
            }
        }
        int len = rootIndex - inBegin;
        // 划分左右子树的范围, 递归建树
        root.left = build(inorder, inBegin, rootIndex, postorder, postBegin, postBegin + len);
        root.right = build(inorder, rootIndex + 1, inEnd, postorder, postBegin + len, postEnd - 1);
        return root;
    }
}