1. question: 从中序与后序遍历序列构造二叉树（中等）
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal
示例 1:
1
2
| 输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]
|
示例 2:
1
2
| 输入：inorder = [-1], postorder = [-1]
输出：[-1]
|
提示:
1
2
3
4
5
6
7
| 1 <= inorder.length <= 3000
postorder.length == inorder.length
-3000 <= inorder[i], postorder[i] <= 3000
inorder 和 postorder 都由 不同 的值组成
postorder 中每一个值都在 inorder 中
inorder 保证是树的中序遍历
postorder 保证是树的后序遍历
|
2. answers
这道题是二叉树中的基本知识。知道中序和前序、或者中序和后序，可唯一的还原出二叉树。因为通过前序或后序，可知道根节点；通过中序，可知道左右子树。继续递归下去即可。
从理论上来看，还是很容易还原出二叉树的。但是从代码上来说，我不容易想出来，一方面是对这种思路的递归不是很熟悉；另一方面是做的比较少。参考了题解。
首先，通过后序找到根节点还是很容易的，通过中序找到根节点的下标，将其划分为两个子序列也是比较容易的。这个时候，创建还原二叉树的根节点。递归还原左右子序列。
此时，需要两个子序列对应的后序子序列，因为一棵树，无论怎么遍历，其节点个数是一样的；并且后序序列是左右子树完全分开的，因此，也可将后序序列切割成左右子序列，通过中序的子序列长度来切割后序序列，形成后序左右子序列。此时分别对两个中序子序列进行遍历即可。
一个关键点在于，中间其实会生成很多的子序列，也就是子数组，这些是当做递归中的参数传递的。生成这么多的数组是不现实的，可传递下标索引。因此，需要四个参数，中序子序列的首尾下标，后续子序列的首尾下标。
代码如下所示：
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
| public class Solution_0063_02 {
public static TreeNode recurTree(int[] inorder, int inLeft, int inRight, int[] postorder, int ptLeft, int ptRight) {
if(inLeft == inRight) return new TreeNode(inorder[inLeft]);
TreeNode root = new TreeNode(postorder[ptRight]);
int rootIndex = 0;
for (int i = 0; i < inorder.length; i++) {
if(inorder[i] == root.val) {
rootIndex = i;
break;
}
}
int postIndex = rootIndex - 1 - inLeft + 1;
postIndex = ptLeft + postIndex - 1;
if(rootIndex == inLeft) root.left = null;
else root.left = recurTree(inorder, inLeft, rootIndex - 1, postorder, ptLeft, postIndex);
if(rootIndex == inRight) root.right = null;
else root.right = recurTree(inorder, rootIndex + 1, inRight, postorder, postIndex + 1, ptRight - 1);
return root;
}
public static TreeNode buildTree(int[] inorder, int[] postorder) {
return recurTree(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
}
public static void main(String[] args) {
System.out.println();
int[] inorder = {-1};
int[] postorder = {-1};
TreeNode root = buildTree(inorder, postorder);
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(queue.size() > 0) {
int length = queue.size();
while(length-- > 0) {
root = queue.poll();
System.out.print(root.val + "\t");
if(root.left != null) queue.offer(root.left);
if(root.right != null) queue.offer(root.right);
}
}
}
}
|
3. 备注
参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。
