题目描述

原题链接：剑指 Offer 07. 重建二叉树

题干

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

示例输入1

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
1
2

示例输入2

Input: preorder = [-1], inorder = [-1]
Output: [-1]
1
2

约束

0 <= 节点个数 <= 5000

解题思路

首先是二叉树遍历的思路

• 前序遍历

  • 根节点
  • 左子节点
  • 右子节点

• 中序遍历

  • 左子节点
  • 根节点
  • 右子节点

思路1——递归

利用中序遍历的特点

遍历前序遍历查找根节点的同时进行递归建树即可，思路如图所示

代码实现——Java

思路1

public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        Map<Integer, Integer> indexMap = new HashMap<>();
        int len = preorder.length;
        for (int i=0; i<len; i++) indexMap.put(inorder[i], i);

        return recursion(preorder, indexMap, 0, len-1, 0, len-1, len);
    }

    /**
     *
     * @param preorder  二叉树的前序遍历
     * @param indexMap  中序遍历中 值到下标的映射
     * @param pre_left  当前子树在前序遍历数组中的下标左边界
     * @param pre_right  当前子树在前序遍历数组中的下标右边界
     * @param in_left  当前子树在中序遍历数组中的下标左边界
     * @param in_right  当前子树在中序遍历数组中的下标右边界
     * @param len 子树长度
     * @return
     */
    public TreeNode recursion(int[] preorder, Map<Integer, Integer> indexMap,
                              int pre_left, int pre_right, int in_left, int in_right, int len) {
        if (len == 0) return null;
        TreeNode root = new TreeNode(preorder[pre_left]);
        int in_root = indexMap.get(preorder[pre_left]);  // 获得根节点在中序遍历中的坐标
        int len_left = in_root - in_left, len_right = in_right - in_root;
        root.left = recursion(preorder, indexMap, 
                pre_left+1, pre_left+len_left, in_left, in_root-1, len_left);
        root.right = recursion(preorder, indexMap,
                pre_left+len_left+1, pre_right, in_root+1, in_right, len_right);
        
        return root;
    }
}
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
26
27
28
29
30
31
32
33
34