链接

剑指 Offer 07. 重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如，给出

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

返回如下的二叉树：

  1.      3
  2.   / \
  3.  9  20
  4.    /  \
  5.   15   7

限制：
0 <= 节点个数 <= 5000

解答

  • 前序遍历的特点：[ 根节点 | 左子树 | 右子树 ]，[ 3 | 9 | 20 15 7 ]
  • 中序遍历的特点：[ 左子树 | 根节点 | 右子树 ], [ 9 | 3 | 15 20 7 ]

结合前序遍历和中序遍历的特点。

  1. 前序遍历的首个节点为 root 的值

  2. 在中序遍历中寻找 root 的值对应的下标，即可将中序遍历分为:[ 左子树 | 根节点 | 右子树 ]

    这样就可以确认三个节点的关系，重建当前二叉树：
    根节点的子树的遍历也同样满足中序遍历和前序遍历的特点: 前序遍历 [ 20 | 25 | 7 ]，中序遍历 [ 15 | 20 | 7 ]
    同样可以安装上面的步骤重建子树，而重复的工作就可以联想到递归
    递归流程：
    利用 preindex 指向前序遍历 preorder 的下标，在递归中依次增加 preindex，preindex++，可以依次重建左子树，再重建右子树。
    在每一轮递归中，获取 preindex 在前序遍历中指向的值，然后在中序遍历中，查找该值对应的下标，将中序遍历分为 [ 左子树 | 根节点 | 右子树]，然后依次重建左子树和右子树。

    1. class Solution {
    2. int[] preorder;
    3. int preIndx; 
    4. public TreeNode buildTree(int[] preorder, int[] inorder) {
    5.     this.preorder = preorder;
    6.     preIndx = 0;
    7.     return rebuild(inorder, 0, inorder.length - 1);
    8. }
    10. private TreeNode rebuild(int[] inorder, int lo, int hi) {
    11.     // 递归终止的条件，
    12.     if (lo > hi ||  preIndx >= preorder.length)
    13.         return null;
    14.     // 获取前序遍历的值，该值是当前root的值。
    15.     int val = preorder[preIndx];
    16.     // 在中序遍历中，查找该值对应的下标，将中序遍历分为 [ 左子树 | 根节点 | 右子树]
    17.     int indx = lo;
    18.     while(indx <= hi && inorder[indx] != val){
    19.         indx ++;
    20.     }
    21.     TreeNode root = new TreeNode(val);
    22.     // 将preIndex 值向下一个值
    23.     preIndx ++;
    24.     // 重建左子树
    25.     root.left = rebuild(inorder, lo, indx-1);
    26.     // 重建右子树
    27.     root.right = rebuild(inorder, indx+1, hi);
    28.     return root;
    29. }
    30. }

    执行结果：通过
    执行用时：4 ms, 在所有 Java 提交中击败了50.77%的用户
    内存消耗：39.9 MB, 在所有 Java 提交中击败了100.00%的用户

    代码优化

    在上面的代码中，每次需要循环遍历 inorder 数组，来查找当前子树的 root 值，利用 map 来提高查询时间。同时也将代码逻辑进行优化。

  1. class Solution {
  2.     Map<Integer, Integer> inorederMap = new HashMap<>();
  3.     int[] preorder;
  4.     public TreeNode buildTree(int[] preorder, int[] inorder) {
  5.        this.preorder = preorder;
  6.        for(int i = 0; i < inorder.length; i ++){
  7.            inorederMap.put(inorder[i], i);
  8.        }
  9.         return rebuild(0, 0, preorder.length - 1);
  10.     }
  11.     private TreeNode rebuild(int rootIndx, int inLeft, int inRight) {
  12.         // 边界条件
  13.         if(inLeft > inRight) return null;
  14.         // 当前 root 的值
  15.         int val = preorder[rootIndx];
  16.         // 中序遍历中 root 值的下标
  17.         int index = inorederMap.get(val);    
  18.         TreeNode root = new TreeNode(val);
  19.         // 重建左子树
  20.         root.left = rebuild(rootIndx+1, inLeft, index-1);
  21.         // 重建右子树
  22.         root.right = rebuild(rootIndx + (index - inLeft) + 1, index + 1, inRight);
  23.         return root;
  24.     }
  27. }