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

1、题目

2、分析

这道题的做法和第105题：从中序与前序遍历序列构造二叉树。一样的解法。
只要找到中序遍历和后序遍历的规则，关键是找出迭代的索引位置就可以了。

3、代码

/**
 * 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 build(inorder, 0, inorder.length - 1, 
                     postorder, 0, postorder.length - 1);
    }

    private TreeNode build(int[] inorder, int inStart, int inEnd,
                           int[] postorder, int postStart, int postEnd){
        if (postStart > postEnd){
            return null;
        }
        int index = -1;
        int rootVal = postorder[postEnd];
        for (int i = inStart; i <= inEnd; i++){
            if (inorder[i] == rootVal){
                index = i;
                break;
            }
        }
        
        int rightSize = inEnd - index;
        TreeNode root = new TreeNode(rootVal);
        root.left = build(inorder, inStart, index - 1,
                          postorder, postStart, postEnd - rightSize - 1);
        root.right = build(inorder, index + 1, inEnd,
                           postorder, postEnd - rightSize, postEnd - 1);
        return root;
    }
}