重建二叉树

题目链接-来源：力扣（LeetCode）

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

例如，给出

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

3
/
9 20
/
15 7

思路：

经典二叉树题。给出一个中序序列和一个前序（后序）序列，建树（注意只有前序、后序序列的话无法唯一地建立一棵二叉树）。此类问题只要想办法定位根节点即可。
对于本题，前序序列中的每一个节点，一定是后续子树的根节点，那么在中序序列中找到这个根节点，左侧即为左子树，右侧即为右子树。对每一个子树递归地重复这个建树过程即可。
注意到不管是前序、中序还是后序序列，一个子树当中的所有元素总是紧邻地出现在一起，那么我们只需要分别记录两个序列中该子树的起始元素的指针、末尾元素的指针，就能在两个序列中划定子树范围，从而递归地执行。

时间复杂度：O(n)
空间复杂度：O(n)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        if (n == 0) {
            return null;
        }
        return buildHelper(preorder, 0, n - 1, inorder, 0, n - 1);
    }
    
    private TreeNode buildHelper(int[] preorder, int pfi, int pei, int[] inorder, int ifi, int iei) {
        if (pfi > pei || ifi > iei) {
            return null;
        }
        int rootVal = preorder[pfi];
        TreeNode root = new TreeNode(rootVal);
        for (int i = 0; i <= iei - ifi; i++) {
            if (rootVal == inorder[ifi + i]) {
                root.left = buildHelper(preorder, pfi + 1, pfi + i, inorder, ifi, ifi + i - 1);
                root.right = buildHelper(preorder, pfi + i + 1, pei, inorder, ifi + i + 1, iei);
                return root;
            }
        }
        return root;
    }
}