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

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
        if(inorder.length==0||postorder.length==0) return null;
        return traversal(inorder,0,inorder.length,postorder,0,postorder.length);
    }
    public TreeNode traversal(int []inorder,int inorderBegin,int inorderEnd,int[]postorder,int postorderBegin,int postOrderEnd){
        if(postorderBegin==postOrderEnd) return null;
        int rootValue = postorder[postOrderEnd-1];
        TreeNode root = new TreeNode(rootValue);
        if(postOrderEnd-postorderBegin==1) return root;
        //找到切割点
        int splitIndex;
        for(splitIndex=inorderBegin;splitIndex<inorderEnd;splitIndex++){
            if(inorder[splitIndex]==rootValue) break;
        }
        //切割中序数组
        //左中序区间 左闭右开[leftInorderBegin,leftInorderEnd)
        int leftInorderBegin = inorderBegin;
        int leftInorderEnd = splitIndex;
        //右中序区间 左闭右开 [rightInorderBegin,rightInorderEnd)
        int rightInorderBegin=splitIndex+1;
        int rightInorderEnd = inorderEnd;
        //切割后序数组
        //左后序区间
        int leftPostorderBegin = postorderBegin;
        int leftPostorderEnd = postorderBegin+splitIndex-inorderBegin;
        //右后序区间
        int rightPostOrderBegin = postorderBegin+(splitIndex-inorderBegin);
        //排除最后一个元素 因为已经作为节点了
        int rightPostOrderEnd = postOrderEnd-1;
        root.left = traversal(inorder,leftInorderBegin,leftInorderEnd,postorder,leftPostorderBegin,leftPostorderEnd);
        root.right = traversal(inorder,rightInorderBegin,rightInorderEnd,postorder,rightPostOrderBegin,rightPostOrderEnd);
        return root;
        
        
    }
}