1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(0, 0, inorder.length - 1, preorder, inorder);
    }
    public TreeNode build(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) {
        if (inStart > inEnd || preStart > preorder.length - 1) return null;
        int inIndex = 0;
        TreeNode root = new TreeNode(preorder[preStart]);
        for (int i = inStart; i <= inEnd; ++i) {
            if (root.val == inorder[i]) {
                inIndex = i;
                System.out.println(i);
                break;
            }
        }
        root.left = build(preStart + 1, inStart, inIndex - 1, preorder, inorder);
        root.right= build(preStart + inIndex - inStart + 1, inIndex + 1, inEnd, preorder, inorder);
        return root;
    }
}

for (int i = inStart; i <= inEnd; ++i): build每次递归的时候，递归查找范围也要随之变化，根节点在inorder中的范围一定是在[inStart, inEnd]闭区间中的；

  • 如果build递归但是查找范围不变: e.g. for (int i = 0; i < inorder.length; i++)其实也是可以的
  • 如果build递归但是查找范围不变: e.g. `for (int i = inStart; i < inEnd; i++): 这样递归缩小范围，AC速度加快
  • (int i = inStart; i < inEnd; ++i): 如果i < inEnd:这样是不行的，因为可能就是inEnd, 但是这样跳过了.