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

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

    private TreeNode buildNode(int[] inorder,int inLeft,int inRight,int[] postorder,int postLeft,int postRight){
        //没有元素了。
        if(inRight - inLeft < 1){ 
            return null;
        }
        //只有一个元素了。
        if(inRight - inLeft == 1) {
            return new TreeNode(inorder[inLeft]);
        }
        // 后序遍历的最后一个节点是根节点
        int rootVal = postorder[postRight - 1];
        TreeNode rootNode = new TreeNode(rootVal);

        // 在中序遍历中找到根节点的位置
        int rootIndex = 0;
        for (int i = inLeft; i < inRight ; i++) {
            if(inorder[i] == rootVal){
                rootIndex = i;
                break;
            }
        }
        //根据rooIndex划分左右子树
        //划分左右中序数组：根据切割点rootIndex划分中序数组
        //划分左右后序数组：根据中序数组的大小必然是和后序数组的大小是一样的。
        rootNode.left = buildNode(inorder,inLeft,rootIndex,postorder,postLeft,postLeft + (rootIndex - inLeft));
        rootNode.right = buildNode(inorder,rootIndex + 1,inRight,postorder,postLeft + (rootIndex - inLeft), postRight - 1);
        return rootNode;
    }
    
    
    
    
    
    
    
    
    
    
    
    
    
    
}