Leetcode(105) Construct Binary Tree from Preorder and Inorder Traversal

发表于 | 更新于 | 分类于

Description:

Given preorder and inorder traversal of a tree, construct the binary tree. Note: You may assume that duplicates do not exist in the tree. For example, given

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

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

解法:

题意简洁明了，即根据二叉树的前序遍历结果与中序遍历结果还原二叉树。（倒吸一口凉气啊，我真的对递归有阴影）。首先分析各顺序遍历的特点，具体如下：

  • 特性A，对于前序遍历，第一个肯定是根节点；
  • 特性B，对于后序遍历，最后一个肯定是根节点；
  • 特性C，利用前序或后序遍历，确定根节点，在中序遍历中，根节点的两边就可以分出左子树和右子树；
  • 特性D，对左子树和右子树分别做前面3点的分析和拆分，相当于做递归，我们就可以重建出完整的二叉树；

我们以一个例子做一下这个过程，假设：

  • 前序遍历的顺序是: CABGHEDF
  • 中序遍历的顺序是: GHBACDEF

第一步，我们根据特性A，可以得知根节点是C，然后，根据特性C，我们知道左子树是：GHBA，右子树是：DEF。

1
2
3
    C
 /     \
GHBA   DEF

第二步，取出左子树，左子树的前序遍历是：ABGH，中序遍历是：GHBA，根据特性A和C，得出左子树的父节点是A，并且A没有右子树。

1
2
3
4
5
6

          C
        /    \
       A    DEF
      /
    GBH

第三步，使用同样的方法，前序是BGH，中序是GBH，得出父节点是B，G和H分别是左右节点。

1
2
3
4
5
6
7
8

             C
          /     \
         A    DEF
        /
       B
     /    \
    G      H

第四步，回到右子树，它的前序是EDF，中序是DEF，依然根据特性A和C，得出父节点是E，左右节点是D和F。

1
2
3
4
5
6
7
           C
        /     \
       A        E
      /       /    \
     B       D      F
   /    \
  G      H

到此，我们得到了这棵完整的二叉树，因此，它的后序遍历就是：GHBADFEC。

那么，思路变得简单了（0.0），即对于现有的序列，先确定根节点，根节点的左子树，根节点的右子树序列，然后在各子树中递归建树。递归的终止条件为序列为空（体现在起始值与终止值上）。

具体实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        TreeNode res = mybuild(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
        return res;
    }

    private TreeNode mybuild(int[] preorder, int startpre, int endpre, int[] inorder, int startin, int endin) {
        if (startpre > endpre || startin > endin) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[startpre]);
        for (int i = startin; i <= endin; i++) {
            if (inorder[i] == root.val) {
                root.left = mybuild(preorder, startpre + 1, startpre + i - startin, inorder, startin, i - 1);
                root.right = mybuild(preorder, startpre - startin + i + 1, endpre, inorder, i + 1, endin);
            }
        }
        return root;
    }
}