面试题7: 重建二叉树

package cn.zxy.interview;

import java.util.Arrays;

/**
 * 分析:
 * 要求: 根据前序和中序遍历序列重建二叉树
 * 前序: 根-->左-->右
 * 中序: 左-->根-->右
 * 一个前序遍历序列可分为三部分: 第一个元素是根节点, 后面一段是左子树的前序遍历, 最后一段是右子树的前序遍历
 * 一个中序遍历序列可分为三部分: 前面一段是左子树的中序遍历 , 中间某个元素是根节点, 最后一段是右子树的中序遍历
 *
 * 每次递归就能重建一个节点: 根节点 -- 直接确定
 *                       左孩子 -- 左子树根节点
 *                       右孩子 -- 右子树根节点
 *
 * 根据前序确定的根节点元素, 在中序序列中找出根节点元素位置i,
 * 前序分段: 左子树前序1~i, 右子树前序i+1, end
 * 中序分段: 左子树中序0~i-1, 右子树中序i+1, end
 *
 * 注意: 这里使用copyOfRange()方法, from是闭区间, to是开区间, 因此i-->i+1, i-1-->i
 *
 * 关键点: 祖宗节点的左节点就是左子树的根节点; 祖宗节点的右节点就是右子树的根节点
 *
 * 等待补充: 传入边界索引, 不新建立数组
 */


public class A07_ReConstructBinaryTree {
    // 内部类定义树节点
    private static class TreeNode{
        private int value;
        private TreeNode lchild;
        private TreeNode rchild;
    }

    public static TreeNode reConstructBinaryTree(int[] pre, int[] in){
        // 终止条件
        if(pre == null || in == null || pre.length == 0 || in.length == 0) return null;
        if(pre.length != in.length) return null;

        TreeNode root = new TreeNode();
        root.value = pre[0];
        root.lchild = null;
        root.rchild = null;

        // 确定根节点元素在中序大的位置
        for (int i = 0; i < in.length; i++) {
            if(pre[0] == in[i]){
                int[] leftSubTreePre = Arrays.copyOfRange(pre, 1, 1+i);
                int[] leftSubTreeIn = Arrays.copyOfRange(in, 0, i);
                int[] rightSubTreePre = Arrays.copyOfRange(pre, i+1, pre.length);
                int[] rightSubTreeIn = Arrays.copyOfRange(in, i+1, in.length);
                root.lchild = reConstructBinaryTree(leftSubTreePre, leftSubTreeIn);
                root.rchild = reConstructBinaryTree(rightSubTreePre, rightSubTreeIn);
            }
        }
        return root;
    }

    public static void main(String[] args) {
        int[] pre = {1,2,4,7,3,5,6,8};
        int[] in =  {4,7,2,1,5,3,8,6};
        TreeNode rootNode = reConstructBinaryTree(pre, in);

    }
}