剑指offerJZ7题 重建二叉树
描述
剑指offerjz7题
给定节点数为 n 的二叉树的前序遍历和中序遍历结果,请重建出该二叉树并返回它的头结点。
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建出如下图所示。
方法一:递归
思路:前序遍历数组第一个即是根节点,第二个是根节点的左节点。在中序遍历数组中找到根节点,根节点前面的元素个数便是根节点左子树的元素个数,根节点后面的元素个数即是根节点右子树的元素个数。已知根节点左右子树的元素个数,再回到前序遍历数组,即可找到根节点的右节点。
代码实现:
1 | /* |
方法二:利用栈
思路:在前序遍历数组中,后一个元素(后者)可能是前一个元素(前者)的三种关系:
1.后者为前者的左节点。
2.后者为前者的右节点(当前者没有左节点的时候)。
3.后者为前者祖先节点的右节点 (当前者没有子节点)。
同样,在中序遍历数组中, 后一个元素(后者)也可能是前一个元素(前者)的三种关系:
1.后者为前者的右节点。
2.后者为前者的父节点。(当前者没有右节点,且前者为后者的左节点时)
3.后者为前者的非父祖先节点。(当前者没有右节点,且前者为其父节点的右节点时)
利用这六种关系,并加上栈存放祖先节点,我们可以对前序数组进行遍历,并结合中序数组进行位置判断,过程就像是对二叉树进行前序遍历。
代码实现:
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66 public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param preOrder int整型一维数组
* @param vinOrder int整型一维数组
* @return TreeNode类
*/
public TreeNode reConstructBinaryTree (int[] pre, int[] vin) {
//首先考虑特殊情况,为零返回空。
int length = pre.length;
if (length == 0) {
return null;
}
TreeNode temp = new TreeNode(pre[0]);
TreeNode root = temp;
Stack<TreeNode> stack = new Stack<>();
for (int i = 1, j = 0; i < length; i++) {
/* 根据中序遍历的规律可知,vin[0]是二叉树最靠左下方的节点,我们
遍历前序数组,根据前序遍历的规律可知,在前序数组
遇到vin[0]及以前,后一个数字就是前一个数字的左节点。当我们
在前序数组找到vin[0]时,此时vin[0]便没有左节点。那么根据前文
总结的前序遍历中的三种情况,除去后者为前者左节点这一情况,还
剩两种情况。此时temp.val == vin[0], 进入else根据中序遍历数组判断
实际是哪种情况。经过第一轮查找之后,后面寻找到的vin[j]为当前
子树的最靠左下方的节点。
*/
if (temp.val != vin[j]) {
temp.left = new TreeNode(pre[i]);
stack.push(temp);
temp = temp.left;
/* (前者指temp, 后者指不同数组中temp的后一位)根据后
文可知,进入else判断的节点,在前序遍历数组中与其后
节点还存在两种可能:
1.后者为前者的右节点
2.后者为前者祖先节点的右节点。
第一种情况的优先级高于第二种情况,也就是说,如果前者存在右
节点,那就属于第一种情况。我们就可以通过中序遍历数组来判
断。因为经过if语句的筛选,我们知道当前temp节点是其父节点的
左节点,所以可以排除中序遍历中后者是前者(temp)祖先节点
这一情况。
所以在中序遍历数组种,后者和前者也存在两种可能:
1.后者为前者的右节点。
2.后者为前者的父节点。
同样,情况一的优先级高于情况二,所以我们可以通过判断中序
遍历数组中前后者的关系,来判断前序遍历中前后者的关系。
要是通过中序遍历数组中,后者与栈(栈中存放着父节点)进行
比较,要是后者是前者的父节点,则说明前者没有右节点,那么
在前序遍历数组中,后者就只剩下一种可能,即为前者祖先节点
的右节点。要是中序遍
历数组中后者不是前者的父节点,那么就可以确定前者存在右节
点,那么前序遍历中后者就是前者temp的右节点。
} else {
j++;
while (!stack.isEmpty() && stack.peek().val == vin[j]) {
temp = stack.pop();
j++;
}
temp.right = new TreeNode(pre[i]);
temp = temp.right;
}
}
return root;
}
}