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

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
        int n = inorder.length;
        TreeNode root = buildTree(inorder,postorder,0,n-1,0,n-1);
        //1.postorder的末端值为根节点，利用该值在中序数组中找到根节点的位置rootIndex
        //2.以rootIndex为界，inorder数组中instart至rootIndex-1是左子树，rootIndex+1至inend是右子树。
        //2.以postStart+（rootIndex-inStart）为界，postorder数组中poststart至postStart+（rootIndex-inStart）-1是左子树，postStart+（rootIndex-inStart）至end-1是右子树
        return root;
    }
    public TreeNode buildTree(int[] inorder, int[] postorder,int inStart, int inEnd, int postStart, int postEnd){
        int rootIndex = inStart;
        TreeNode root = new TreeNode(postorder[postEnd]);
        for(int i = inStart; i <= inEnd; i++){
            if(inorder[i] == postorder[postEnd]){
                rootIndex = i;
                break;
            }
        }
        int offset = rootIndex-inStart;
        if(inStart<rootIndex){
            //说明有左子树
            root.left = buildTree(inorder,postorder,inStart,rootIndex-1,postStart,postStart+offset-1);
        }
        if(rootIndex<inEnd){
            //说明有右子树
            root.right = buildTree(inorder,postorder,rootIndex+1,inEnd,postStart+offset,postEnd-1);
        }
        return root;
    }
}