剑指 Offer 07. 重建二叉树

原题链接

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return recur(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }
    public TreeNode recur(int[] preorder, int p_start, int p_end, int[] inorder, int i_start, int i_end){
        //截止条件
        if(i_start > i_end) return null;
        int rootVal = preorder[p_start];
        int i_root_index = 0;
        for(int i = 0; i <= i_end; i++){
            if(inorder[i] == rootVal){
                i_root_index = i;
                break;
            }
        }
        //计算leftNum
        int leftNum = i_root_index - i_start;
        TreeNode root = new TreeNode(rootVal);
        root.left = recur(preorder, p_start + 1, p_start + leftNum, inorder, i_start, i_root_index - 1);
        root.right = recur(preorder, p_start + leftNum + 1, p_end, inorder, i_root_index + 1, i_end);
        return root;
    }
}