2021/2/13 剑指 Offer 07. 重建二叉树

题目描述

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

示例

输入

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回值

    3
   / \
  9  20
    /  \
   15   7

解题思路

1. 先从前序遍历中获取第一个值，如示例中 preorder[0] == 3，然后在中序遍历中找 3 所在的位置。
2. 得到 3 在 inorder中的位置 i 为 1，即 3 == inorder[1]，由中序遍历的特性“左 -> 中 -> 右”我们可以得知，在中序遍历中，inorder[1] 左边的是左叶子，右边的是右叶子。
   
3. 又由前序遍历的特性“中 -> 左 -> 右”我们可以得知在 preorder 中每个元素的左子节点都在自己的右边。而右子节点则在 inorder 中得到的左叶子长度 + 根节点索引 + 1 处。
4. 递归地执行，边界条件为当前叶子是否还有节点。

Java代码实现

class Solution {
    int[] preorder;
    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for (int i = 0; i < inorder.length; ++i) {
            map.put(inorder[i], i);
        }
        return func(0, 0, inorder.length - 1);
    }

    private TreeNode func(int root, int left, int right) {
        // 边界条件
        if (left > right) return null;
        TreeNode rootNode = new TreeNode(preorder[root]);
        // 寻找根节点元素在 inorder 中的索引，划分左右子叶
        int i = map.get(preorder[root]);
        rootNode.left = func(root + 1, left, i - 1);
        // i - left 意思是左子节点的长度，root + i - left + 1 意思是右子节点位置
        rootNode.right = func(root + i - left + 1, i + 1, right);
        return rootNode;
    }
}