剑指 Offer 07. 重建二叉树

public class offer07 {

    private static Map<Integer,Integer> indexMap;
    public static void main(String[] args) {
        // TODO Auto-generated method stub

        int[] preorder = new int[]{3,9,20,15,7};
        int[] inorder = new int[]{9,3,15,20,7};
        TreeNode tree = buildTree(preorder,inorder);
        System.out.println(tree);
    }

    /**
     * 思路：主要是递归的定位到根节点
     * @param preorder
     * @param inorder
     * @return
     */
    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        //构造哈希映射，帮助我们快速定位根节点
        indexMap = new HashMap<Integer,Integer>();
        for(int i=0;i<n;i++){
            indexMap.put(inorder[i], i);
        }
        return myBuildTree(preorder,inorder,0,n-1,0,n-1);
    }
    
    
    /**
     * 递归方式
     * 先根据先序遍历确认根节点，然后找出根节点在中序遍历的位置，从而确定左子树的长度和右子树的长度，对应到先序遍历中也能找出对应的左子树和右子树，
     * 分别递归左子树和右子树，重复上面步骤。
     * 
     * @param preorder
     * @param inorder
     * @param preorder_left
     * @param preorder_right
     * @param inorder_left
     * @param inorder_right
     * @return
     */
    public static TreeNode myBuildTree(int[] preorder,int[] inorder,int preorder_left,int preorder_right,int inorder_left,int inorder_right){
        if(preorder_left>preorder_right){
            return null;
        }
        
        //前序遍历中的第一个节点就是根节点
        int preorder_root = preorder_left;
        //在中序遍历中定位根节点
        int inorder_root = indexMap.get(preorder[preorder_root]);
        
        //先把根节点建立出来
        TreeNode root = new TreeNode(preorder[preorder_root]);
        //得到左子树中的节点数目
        int size_left_subtree = inorder_root - inorder_left;
        //递归的构造左子树，并连接到根节点
        //先序遍历中【从左边界+1 开始的size_left_subtree】个元素就对应了中序遍历中【从左边界开始到根节点定位-1】的元素
        root.left = myBuildTree(preorder,inorder,preorder_left+1,preorder_left+size_left_subtree,inorder_left,inorder_root-1);
        
        //递归的构造右子树，并连接到根节点
        //先序遍历中【 从左边界+1  + 左子树节点数目  对应 开始 到右边界】的元素对应了中序遍历中  【从左边界开始 到 根节点-1】的元素
        root.right = myBuildTree(preorder,inorder,preorder_left+size_left_subtree+1,preorder_right,inorder_root+1,inorder_right);
        
        return root;
    }
    
    
}

class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x){
        val = x;
    }
}