7. 重建二叉树

题目链接

Leetcode

题目描述

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

解题思路

前序遍历的第一个值为根节点的值，使用这个值将中序遍历结果分成两部分，左部分为树的左子树中序遍历结果，右部分为树的右子树中序遍历的结果。然后分别对左右子树递归地求解。

设根在中序遍历中的下标为 inIndex，左子树的节点数 leftTreeSize = inIndex - inL。在前序遍历中，根后面紧跟着的 leftTreeSize 个值是左子树，剩下的是右子树，由此得到递归时左右子树在前序数组中的范围。用哈希表记录中序遍历中每个值的下标，找根的位置只需要 O(1)，整体时间复杂度为 O(N)。

// 缓存中序遍历数组每个值对应的索引
private Map<Integer, Integer> indexForInOrders = new HashMap<>();

public TreeNode deduceTree(int[] preorder, int[] inorder) {
    for (int i = 0; i < inorder.length; i++)
        indexForInOrders.put(inorder[i], i);
    return deduceTree(preorder, 0, preorder.length - 1, 0);
}

private TreeNode deduceTree(int[] pre, int preL, int preR, int inL) {
    if (preL > preR)
        return null;
    TreeNode root = new TreeNode(pre[preL]);
    int inIndex = indexForInOrders.get(root.val);
    int leftTreeSize = inIndex - inL;
    root.left = deduceTree(pre, preL + 1, preL + leftTreeSize, inL);
    root.right = deduceTree(pre, preL + leftTreeSize + 1, preR, inL + leftTreeSize + 1);
    return root;
}