来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof
题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
1
2
3
4
5
| 3
/ \
9 20
/ \
15 7
|
限制：
0 <= 节点个数 <= 5000
我的解题
思路
首先确定两种遍历方式的区别：
- 前序遍历：根节点->左节点->右节点
- 中序遍历：左节点->根节点->右节点
因此，在中序遍历中，在根节点之前被访问的节点都位于左子树，在根节点之后被访问的节点都位于右子树。同时前序遍历的数据顺序对于跟节点来说，等于如下结构【根节点】【所有左节点】【所有右节点】，因此，在通过跟节点从中序遍历中得到跟节点的左右字节点队列与个数后，能根据左右字节点的数量从前序遍历中分解出左节点队列和右节点队列，到了这步通过迭代即可遍历树。
其实我只到两种遍历的区别，没有第一时间意识到通过宏观的角度将数组分成左右两个节点的队列，太久没有接触树的概念生疏了。
结果
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
|
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder == null || preorder.length == 0) {
return null;
}
Map<Integer, Integer> indexMap = new HashMap<Integer, Integer>();
int length = preorder.length;
for (int i = 0; i < length; i++) {
indexMap.put(inorder[i], i);
}
TreeNode root = buildTree(preorder, 0, length - 1, inorder, 0, length - 1, indexMap);
return root;
}
public TreeNode buildTree(int[] preorder, int preorderStart, int preorderEnd, int[] inorder, int inorderStart, int inorderEnd, Map<Integer, Integer> indexMap) {
if (preorderStart > preorderEnd) {
return null;
}
int rootVal = preorder[preorderStart];
TreeNode root = new TreeNode(rootVal);
if (preorderStart == preorderEnd) {
return root;
} else {
int rootIndex = indexMap.get(rootVal);
int leftNodes = rootIndex - inorderStart, rightNodes = inorderEnd - rootIndex;
TreeNode leftSubtree = buildTree(preorder, preorderStart + 1, preorderStart + leftNodes, inorder, inorderStart, rootIndex - 1, indexMap);
TreeNode rightSubtree = buildTree(preorder, preorderEnd - rightNodes + 1, preorderEnd, inorder, rootIndex + 1, inorderEnd, indexMap);
root.left = leftSubtree;
root.right = rightSubtree;
return root;
}
}
}
|
最优解
思路
第一个通过迭代的思路同上。因此这里介绍另一种方法：迭代。
例如要重建的是如下二叉树。
1
2
3
4
5
6
7
8
9
| 3
/ \
9 20
/ / \
8 15 7
/ \
5 10
/
4
|
其前序遍历和中序遍历如下。
preorder = [3,9,8,5,4,10,20,15,7]
inorder = [4,5,8,10,9,3,15,20,7]
前序遍历的第一个元素 3 是根节点，第二个元素 9 可能位于左子树或者右子树，需要通过中序遍历判断。
中序遍历的第一个元素是 4 ，不是根节点 3，说明 9 位于左子树，因为根节点不是中序遍历中的第一个节点。同理，前序遍历的后几个元素 8、5、4 也都位于左子树，且每个节点都是其上一个节点的左子节点。
前序遍历到元素 4，和中序遍历的第一个元素相等，说明前序遍历的下一个元素 10 位于右子树。那么 10 位于哪个元素的右子树？从前序遍历看，10 可能位于 4、5、8、9、3 这些元素中任何一个元素的右子树。从中序遍历看，10 在 8 的后面，因此 10 位于 8 的右子树。把前序遍历的顺序反转，则在 10 之前的元素是 4、5、8、9、3，其中 8 是最后一次相等的节点，因此前序遍历的下一个元素位于中序遍历中最后一次相等的节点的右子树。
根据上述例子和分析，可以使用栈保存遍历过的节点。初始时令中序遍历的指针指向第一个元素，遍历前序遍历的数组，如果前序遍历的元素不等于中序遍历的指针指向的元素，则前序遍历的元素为上一个节点的左子节点。如果前序遍历的元素等于中序遍历的指针指向的元素，则正向遍历中序遍历的元素同时反向遍历前序遍历的元素，找到最后一次相等的元素，将前序遍历的下一个节点作为最后一次相等的元素的右子节点。其中，反向遍历前序遍历的元素可通过栈的弹出元素实现。
- 使用前序遍历的第一个元素创建根节点。
- 创建一个栈，将根节点压入栈内。
- 初始化中序遍历下标为 0。
- 遍历前序遍历的每个元素，判断其上一个元素（即栈顶元素）是否等于中序遍历下标指向的元素。
- 若上一个元素不等于中序遍历下标指向的元素，则将当前元素作为其上一个元素的左子节点，并将当前元素压入栈内。
- 若上一个元素等于中序遍历下标指向的元素，则从栈内弹出一个元素，同时令中序遍历下标指向下一个元素，之后继续判断栈顶元素是否等于中序遍历下标指向的元素，若相等则重复该操作，直至栈为空或者元素不相等。然后令当前元素为最后一个想等元素的右节点。
- 遍历结束，返回根节点。
结果
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
|
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder == null || preorder.length == 0) {
return null;
}
TreeNode root = new TreeNode(preorder[0]);
int length = preorder.length;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
int inorderIndex = 0;
for (int i = 1; i < length; i++) {
int preorderVal = preorder[i];
TreeNode node = stack.peek();
if (node.val != inorder[inorderIndex]) {
node.left = new TreeNode(preorderVal);
stack.push(node.left);
} else {
while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
node = stack.pop();
inorderIndex++;
}
node.right = new TreeNode(preorderVal);
stack.push(node.right);
}
}
return root;
}
}
|