重建二叉树

问题描述

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
**
例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：

3
/ \
9 20
/ \
15 7

问题分析

对于前序遍历是从根节点进行遍历，中序遍历是需要从左节点进行遍历，然后是根节点，最后才是右节点，对于上述过程对于左子树是同样的问题，所以整个思路就是：

1. 根据前序遍历找到root节点，根据中序遍历找到root节点的左子树和右子树；
2. 递归遍历左子树和右子树；
3. 返回根节点；

代码实现

public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null || inorder == null || preorder.length == 0 || inorder.length == 0){
            return null;
        }
        return rebuild(preorder, 0, preorder.length -1, inorder, 0, inorder.length -1);
    }
    public TreeNode rebuild(int[] preorder, int startPre, int endPre, int[] midorder, int startMid, int endMid){
        //root Node
        TreeNode root = new TreeNode(preorder[startPre]);
        root.left = root.right = null;
        if(startPre == endPre && preorder[startPre] == midorder[startMid]){
            return root;
        }
        int midOrder = startMid;
        //get position which diff left child and right child
        while(midOrder < midorder.length && midorder[midOrder] != preorder[startPre]){
            midOrder++;
        }
        int leftLength = midOrder - startMid;
        int leftPreOder = startPre + leftLength;
        //build left
        if(leftLength >0){
            root.left = rebuild(preorder, startPre + 1, leftPreOder, midorder, startMid, midOrder);
        }
        if(leftLength < endPre - startPre){
            root.right = rebuild(preorder, leftPreOder+1, endPre, midorder, midOrder+1, endMid);
        }
        return root;
    }
}