「剑指 Offer」面试题 6:重建二叉树

Posted by Ink Bai on 2018-11-29     & views

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列 {1, 2, 4, 7, 3, 5, 6, 8} 和中序遍历序列 {4, 7, 2, 1, 5, 3, 8, 6},则重建出如下图所示的二叉树并返回它的头结点。

二叉树

首先了解一下二叉树:有一个根结点,根结点下面最多有两个子结点,分别是左右子结点,二叉输的遍历方式一般有三种:

  • 前序遍历:先访问根结点,再访问左子结点,最后访问右子结点。
  • 中序遍历:先访问左子结点,再访问根结点,最后访问右子结点。
  • 后序遍历:先访问左子结点,再访问右子结点,最后访问根结点。

让我们找一下规律,前序遍历先访问根结点,前序遍历的序列是 {1, 2, 4, 7, 3, 5, 6, 8},所以可以确定,1 就是根结点的值。

中序遍历是先访问左子结点,再访问根结点,上面我们确定了 1 是根结点,那可以说明 1 前面的数字就是左子结点对应的中序遍历序列,1 后面是右子结点的中序遍历序列。

中序遍历

由于左右子结点的数目应该是相同的,我们可以根据中序遍历序列确定前序遍历序列的左右子结点如下图。

前序遍历

代码实现

通过上面的步骤我们已经确定了该二叉树的根结点,左子结点的前序遍历和中序遍历,右子结点的前序遍历和中序遍历,自然可以想到用递归的方法去解决。

首先看一种非常简洁易懂的方法:

/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/

import java.util.Arrays;
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre, int [] in) {
if (pre == null || in == null || pre.length == 0 || in.length == 0 || pre.length != in.length) {
return null;
}

// 指定根节点的值
TreeNode node = new TreeNode(pre[0]);
for (int i = 0; i < in.length; i++) {
if (in[i] == node.val) {
// 递归得到左右子结点重建后的二叉树
node.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i+1), Arrays.copyOfRange(in, 0, i));
node.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i+1, pre.length), Arrays.copyOfRange(in, i+1,in.length));
}
}

return node;
}
}

这种方法非常好理解,缺点是并不是在原来的数组上操作,而是使用了 copyOfRange 方法复制了原来的数组,下面这种方法是直接在原来的数组上操作的,但是下标边界直接看不是很明白,需要配合画图才能理解。

/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/

import java.util.Arrays;
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre, int [] in) {
TreeNode root = reConstructBinaryTree(pre, 0, pre.length - 1, in, 0, in.length - 1);
return root;
}

private TreeNode reConstructBinaryTree(int [] pre, int startPre, int endPre, int [] in, int startIn, int endIn) {
// 超出界限没有子结点了
if(startPre > endPre || startIn > endIn) {
return null;
}
TreeNode root = new TreeNode(pre[startPre]);
for(int i = startIn; i <= endIn; i++) {
if(in[i] == pre[startPre]) {
root.left = reConstructBinaryTree(pre, startPre + 1, startPre + i - startIn, in, startIn, i - 1);
root.right = reConstructBinaryTree(pre, startPre + i -startIn + 1, endPre, in, i + 1, endIn);
}
}
return root;
}
}

下面解释一下代码,首先我们定义一个递归方法,这个方法会输入 pre 和 in,以及它们分别对应的起始下标,第一次调用就是:

TreeNode root = reConstructBinaryTree(pre, 0, pre.length - 1, in, 0, in.length - 1)

递归什么时候结束呢,只要到达最后的叶子结点就结束了,判断的条件就是开始下标必须大于结束下标,不满足就返回 null,代表已经没有子结点了。

if(startPre > endPre || startIn > endIn)

然后对 in 即中序遍历的序列循环,因为这样我们可以找出根结点的位置,从而可以区分出左右子结点,当循环到根结点位置时下标位置如下图所示:

中序遍历

前序遍历

从中序遍历图中可以得到:
左子结点长度 = i - startIn
右子结点长度 = endIn - i

所以对于左子结点来说:
前序遍历起始下标 = (startPre + 1, startPre + i - startIn)
中序遍历起始下标 = (startIn, i - 1)

对于右子结点来说:
前序遍历起始下标 = (startPre + i - startIn + 1, endPre)
中序遍历起始下标 = (i + 1, endIn)

通过上面分析我们可以实现用很简洁的代码完成了整个递归过程,递归的实现很容易想到,但是动手实现并且简洁地实现却是千难万难,这个时候我们就可以结合画图来快速地解决问题。