题目链接

剑指 Offer 07. 重建二叉树

思路

递归建树，思路与【DFS】LeetCode 105. 从前序与中序遍历序列构造二叉树相同。

代码

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return this.buildTree(preorder, 0, preorder.length - 1,
                inorder, 0, inorder.length - 1);
    }

    TreeNode buildTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd){
        if(preEnd < preStart){
            return null;
        }

        int mid = find(inorder, preorder[preStart], inStart, inEnd);
        TreeNode node = new TreeNode(preorder[preStart]);

        int leftLength = mid - inStart;
        node.left = buildTree(preorder, preStart + 1, preStart + leftLength,
                inorder, inStart, mid - 1);
        node.right = buildTree(preorder, preStart + 1 + leftLength, preEnd,
                inorder, mid + 1, inEnd);

        return node;
    }

    int find(int[] a, int target, int start, int end){
        for(int i = start; i <= end; i++){
            if(a[i] == target){
                return i;
            }
        }

        return -1;
    }
}