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

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;
        int rootVal = postorder[postorder.length-1]; // 根节点就是后序遍历的最后一个元素
        TreeNode root = new TreeNode(rootVal);
        for(int i = 0; i < inorder.length; i++){
            if(rootVal == inorder[i]){ // 在中序遍历序列中找到根节点
			  // 根据根节点的位置分割数组
                int[] inleft = Arrays.copyOfRange(inorder, 0, i);
                int[] inRight = Arrays.copyOfRange(inorder, i+1, inorder.length);
                int[] postLeft = Arrays.copyOfRange(postorder, 0, i);
                int[] postRight = Arrays.copyOfRange(postorder, i, postorder.length-1);
			  // 分别构建左子树、右子树
                root.left = buildTree(inleft, postLeft);
                root.right = buildTree(inRight, postRight);
                break; // 要停止遍历
            }
        }
        return root;
    }
}