剑指Offer对答如流系列 - 重建二叉树
沉晓Jeffery 人气:2面试题6:重建二叉树
题目描述:
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建出图2.6所示的二叉树并输出它的头结点。二叉树结点的定义如下:
class Node{
int e;
Node left;
Node right;
Node(int x) { e = x; }
}
这道题主要测试你对二叉树性质的了解,非常有代表性,不过在这之前,我们先把二叉树的基本性质捋一遍。
二叉树的基本性质
(1)关于树
树是一种数据结构,它是由n(n>=1)个有限结点组成一个具有层次关系的集合。
树的基本术语有:
- 每个结点有零个或多个子结点
- 没有父节点的结点称为
根节点
- 每一个非根结点有且只有一个
父节点
- 除了根结点外,每个子结点可以分为多个不相交的子树。
- 若一个结点有子树,那么该结点称为子树根的
“双亲”
,子树的根称为该结点的“孩子”
。有相同双亲的结点互为“兄弟”
。 - 一个结点的所有子树上的任何结点都是该结点的后裔。从根结点到某个结点的路径上的所有结点都是该结点的祖先。
- 结点的度:结点拥有的子树的数目
- 叶子结点:度为0的结点
- 分支结点:度不为0的结点
- 树的度:树中结点的最大的度
- 层次:根结点的层次为1,其余结点的层次等于该结点的双亲结点的层次加1
- 树的高度:树中结点的最大层次
- 森林:0个或多个不相交的树组成。对森林加上一个根,森林即成为树;删去根,树即成为森林。
“树”是计算机科学中非常重要的一部分内容,它的变形和应用非常之多。比如说,在做通讯录的时候,Android 工程师往往喜欢用字典树
来存取数据,对于Java后端,有的时候我们处理的数据的时候也需要进行区间的查询,比如说去年你的博客在什么时间段关注你的人增长最快啊,一天中自己的博文阅读量最高的时间段啊,可以采用线段树
来实现。在JDK1.8的HashMap的结构中,当元素超过8个的时候,会转为红黑树
等等。
不过对于Java开发而言,二叉树是基础也是接触较多的一种结构。
(2)关于二叉树
二叉树是每个结点最多有两个子树的树结构。它有五种基本形态:
1)空树;
2)只有根的树,即单结点;
3)有根且有一个左子树;
4)有根且有一个右子树;
5)有根且有一个左子树,有一个右子树。
二叉树的性质有:
- 二叉树第i层上的结点数目最多为2i-1(i>=1)
- 深度为k的二叉树至多有2k-1个结点(k>=1)
- 包含n个结点的二叉树的高度至少为(log2n)+1
在任意一棵二叉树中,若叶子结点的个数为n0,度为2的结点数为n2,则n0=n2+1
第四条的证明: 因为二叉树中所有结点的度数均不大于2,设n0表示度为0的结点个数,n1表示度为1的结点个数,n2表示度为2的结点个数。
三类结点加起来为总结点个数,于是便可得到:n=n0+n1+n2 (公式1)
由度之间的关系可得第二个等式:n=n0*0+n1*1+n2*2+1 即n=n1+2n2+1 (公式2)
将(公式1)(公式2)组合在一起可得到n0=n2+1
了解这第四条性质就差不多了。如果想进一步学习二叉树的性质,不妨去找本《离散数学》?
对二叉树遍历的理解
以这棵树为例:
前序遍历:根结点 —> 左子树 —> 右子树(先遍历根节点,然后左右)
//前序遍历以node为根
public void preOrder(Node node) {
//终止条件
if(node == null) {
return;
}
System.out.println(node.e);
preOrder(node.left);
preOrder(node.right);
}
这棵树的前序遍历为:FCADBEHGM
中序遍历:左子树—> 根结点 —> 右子树(在中间遍历根节点)
//中序以node为根的
public void inOrder(Node node) {
//终止条件
if(node == null) {
return;
}
inOrder(node.left);
System.out.println(node.e);
inOrder(node.right);
}
这棵树的中序遍历为:ACBDFHEMG
后序遍历:左子树 —> 右子树 —> 根结点(最后遍历根节点)
//中序以node为根
public void postOrder(Node node) {
//终止条件
if(node == null) {
return;
}
postOrder(node.left);
postOrder(node.right);
System.out.println(node.e);
}
这棵树的后序遍历为:ABDCHMGEF
层序遍历:
//层序遍历
public void levelOrder() {
Queue<Node> q = new LinkedList<>();
q.add(root);
while( !q.isEmpty() ) {
Node cur = q.remove();
System.out.println(cur.e);
if(cur.left != null)
q.add(cur.left);
if(cur.right != null)
q.add(cur.right); //后出
}
}
这棵树层序遍历为:FCEADHGBM
所谓的前序、中序、后序,就是对根节点而言的,左右的遍历顺序不变,前序就是根节点最先遍历,然后左右;中序就是把根节点放在中间遍历;后序则是把根节点放在最后遍历。
中序遍历能够帮助我们很好地确定根节点的位置,这个就有点可怕了,实际面试的时候,不单单会有给出前序遍历和中序遍历的结果
让你重建二叉树,还有给出后序遍历和中序遍历结果
或者 层序遍历和中序遍历的结果
重建二叉树、
其他的遍历组合均不能还原出二叉树的形状,因为无法确认其左右孩子。例如,前序为AB,后序为AB,则无法确认出,B节点是A节点的左孩子还是右孩子,因此无法还原。
题解
思路:通过前序遍历获得根节点的位置,利用根节点将中序序列分为左子树和右子树,然后不断的递归划分即可。
代码中有解释。
private Node buildTree(int[] pre, int preBegin, int preEnd, int[] mid, int midBegin, int midEnd) {
// 前序遍历确第一个元素为根节点
Node root = new Node(pre[preBegin]);
// 用于标记中序遍历结果中根节点的位置
int midRootLocation= 0;
for (int i = midBegin; i <= midEnd; i++) {
if (mid[i] == pre[preBegin]) {
midRootLocation= i;
break;
}
}
if ( midRootLocation - midBegin >= 1 ) {
// 递归得到左子树
// 中序遍历:左子树—> 根结点 —> 右子树(在中间遍历根节点)
// midRootLocation标记了中序遍历结果中根节点的位置,这个位置两端对应根节点左子树和右子树
// midRootLocation- midBegin 表示该根节点左边的节点的数量
// 前序遍历:根结点 —> 左子树 —> 右子树(先遍历根节点,然后左右)
// preBegin 标记了前序遍历结果中根节点的位置
// preBegin + 1 表示该根节点左子树起始位置
// preBegin + (midRootLocation- midBegin) 表示给根节点左子树结束的位置
Node left = buildTree(pre, preBegin + 1, preBegin + (midRootLocation- midBegin),
mid, midBegin, midRootLocation - 1);
root.left = left;
}
if ( midEnd - midRootLocation >= 1 ) {
// 递归得到右子树
// 原理和上面相同
Node right = buildTree(pre, preEnd - (midEnd - midRootLocation) + 1, preEnd,
mid, midRootLocation+ 1, midEnd);
root.right = right;
}
return root;
}
举一反三
(1)给出后序遍历和中序遍历的结果重建二叉树
思路:通过后序获取根节点的位置,然后在中序中划分左子树和右子树,然后递归划分即可。
形式与上面 给出 前序遍历和中序遍历的结果重建二叉树相同
private Node buildTree(int[] mid, int midBegin, int midEnd, int[] end, int endBegin, int endEnd) {
Node root = new Node(end[endEnd]);
int midRootLocation = 0;
for (int i = midEnd; i >= midBegin; i--) {
if (mid[i] == end[endEnd]) {
midRootLocation = i;
break;
}
}
//还原左子树
if (midRootLocation - midBegin >= 1 ) {
Node left = buildTree(mid, midBegin, midRootLocation - 1, end, endBegin, endBegin + (midRootLocation - midBegin) - 1);
root.left = left;
}
//还原右子树
if (midEnd - midRootLocation >= 1 ) {
Node right = buildTree(mid, midRootLocation + 1, midEnd, end, endEnd - (midEnd - midRootLocation), endEnd - 1);
root.right = right;
}
return root;
}
(2)给出层序遍历和中序遍历结果重建二叉树
思路:
(1)根据层序遍历获取根节点的位置
(2)根据(1)将中序划分为左子树和右子树
(3)根据(2)划分出的左子树和右子树分别在层序遍历中获取其对应的层序顺序
(4)然后递归调用划分。
private Node buildTree(int[] mid, int[] level, int midBegin, int midEnd) {
// 层序遍历的第一个结果是 根节点
Node root = new Node(level[0]);
// 用于标记中序遍历的根节点
int midLocation = -1;
for (int i = midBegin; i <= midEnd; i++) {
if (mid[i] == level[0]) {
midLocation = i;
break;
}
}
if (level.length >= 2) {
if (isLeft(mid, level[0], level[1])) {
Node left = buildTree(mid, getLevelArray(mid, midBegin, midLocation - 1, level), midBegin, midLocation - 1);
root.left = left;
if (level.length >= 3 && !isLeft(mid, level[0], level[2])) {
Node right = buildTree(mid, getLevelArray(mid, midLocation + 1, midEnd, level), midLocation + 1, midEnd);
root.right = right;
}
} else {
Node right = buildTree(mid, getLevelArray(mid, midLocation + 1, midEnd, level), midLocation + 1, midEnd);
root.right = right;
}
}
return root;
}
// 功能 : 判断元素是根节点的左子树节点还是右子树节点
// 参数 : target为根节点 isLeft在中序遍历结果中判断children是根节点的左子树还是右子树
// 返回值 : 如果为左子树节点则为true 否则为false
private boolean isLeft(int[] array, int target, int children) {
boolean findC = false;
for (int temp : array) {
if (temp == children) {
findC = true;
} else if (temp == target) {
return findC;
}
}
return false;
}
// 功能: 将中序序列中midBegin与midEnd的元素依次从level中提取出来,保持level中的元素顺序不变
private int[] getLevelArray(int[] mid, int midBegin, int midEnd, int[] level) {
int[] result = new int[midEnd - midBegin + 1];
int curLocation = 0;
for (int i = 0; i < level.length; i++) {
if (contains(mid, level[i], midBegin, midEnd)) {
result[curLocation++] = level[i];
}
}
return result;
}
// 如果array的begin和end位置之间(包括begin和end)含有target,则返回true。
private boolean contains(int[] array, int target, int begin, int end) {
for (int i = begin; i <= end; i++) {
if (array[i] == target) {
return true;
}
}
return false;
}
加载全部内容