题解 | 从中序与后序遍历序列构造二叉树

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param inorder int整型一维数组 中序遍历序列
     * @param postorder int整型一维数组 后序遍历序列
     * @return TreeNode类
     */
    public TreeNode buildTree (int[] inorder, int[] postorder) {
        // write code here
        return build(inorder, 0, inorder.length-1, postorder, 0, postorder.length-1);

    }

    private TreeNode build(int[]inorder, int iStart, int iEnd, int[]postorder, int pStart, int pEnd) {
        if (iStart > iEnd || pStart > pEnd) return null;
        int val = postorder[pEnd];
        TreeNode root = new TreeNode(val);
        int count = 0;
        for (int i=iStart; i<=iEnd; i++) {
            if (inorder[i] == val) {
                break;
            }
            count++;
        }
        root.left = build(inorder, iStart, iStart + count-1, postorder, pStart, pStart + count-1);
        root.right = build(inorder, iStart + count+1, iEnd, postorder, pStart + count,pEnd-1);
        return root;
    }
}