105 重建二叉树
- 思路
- code

105 重建二叉树

思路

主要解题思路，使用递归的方法<br />    1、前序遍历中第一个元素对应根节点（递归思路，每次都是根节点）<br />    2、根节点在中序遍历中每次将中序遍历平分为两分，左边和右边分别对应一个新的子树<br />    3、递归中止条件，当根节点再往下分子树，子树为空即结束递归

code

class Solution {
     public TreeNode buildTree(int[] preorder, int[] inorder) {
        int start = 0;
        int end = preorder.length-1;
        return buildTreeStep(start,end,start,end,preorder,inorder);
    }
    //递归实现
    public TreeNode buildTreeStep(int preStart ,int preEnd ,int inStart,int inEnd,int[] preorder,int[] inorder){
        if (preEnd<preStart || inEnd<inStart) {
            return null;
        }
        TreeNode treeNode = new TreeNode(preorder[preStart]);
        int pivot  = getCurIndexInInOrder(inorder,inStart,inEnd,preorder[preStart]);
        treeNode.left = buildTreeStep(preStart+1,pivot+preStart,inStart,inStart+pivot-1,preorder,inorder);
        treeNode.right = buildTreeStep(preStart+pivot+1,preEnd,inStart+pivot+1,inEnd,preorder,inorder);
        return treeNode;
    }
    //get pivot index
    public int getCurIndexInInOrder(int[] inorder, int start, int end, int key){
        for(int i=start; i<=end; i++){
            if(inorder[i] == key) return i-start;
        }
        return -1;
    }
}