11##题目地址
22https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
33
4+ > 给出两个序列
5+
6+ #106.从中序与后序遍历序列构造二叉树
7+
8+ 根据一棵树的中序遍历与后序遍历构造二叉树。
9+
10+ 注意:
11+ 你可以假设树中没有重复的元素。
12+
13+ 例如，给出
14+
15+ 中序遍历 inorder = [ 9,3,15,20,7]
16+ 后序遍历 postorder =[ 9,15,7,20,3]
17+ 返回如下的二叉树：
18+
19+ <img src =' ../pics/106. 从中序与后序遍历序列构造二叉树1.png ' width =600 > </img ></div >
20+
421##思路
522
6- 首先回忆一下如何根据两个顺序构造一个唯一的二叉树，相信理论知识大家应该都清楚，就是以后序数组最后一个元素为切割点 ，先切中序数组，根据中序数组，反过来在切后序数组。一层一层切下去，每次后序数组最后一个元素就是节点元素。
23+ 首先回忆一下如何根据两个顺序构造一个唯一的二叉树，相信理论知识大家应该都清楚，就是以 后序数组的最后一个元素为切割点 ，先切中序数组，根据中序数组，反过来在切后序数组。一层一层切下去，每次后序数组最后一个元素就是节点元素。
724
825如果让我们肉眼看两个序列，画一颗二叉树的话，应该分分钟都可以画出来。
926
1027流程如图：
1128
12-
1329<img src =' ../pics/106.从中序与后序遍历序列构造二叉树.png ' width =600 > </img ></div >
1430
1531那么代码应该怎么写呢？
1632
17- 说道一层一层切割 ，就应该想到了递归。
33+ 说到一层一层切割 ，就应该想到了递归。
1834
1935来看一下一共分几步：
2036
2137* 第一步：如果数组大小为零的话，说明是空节点了。
2238
2339* 第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。
2440
25- * 第三步：找到后序数组最后一个元素在后序数组的位置 ，作为切割点
41+ * 第三步：找到后序数组最后一个元素在中序数组的位置 ，作为切割点
2642
2743* 第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）
2844
@@ -35,36 +51,38 @@ https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorde
3551```
3652 TreeNode* traversal (vector<int>& inorder, vector<int>& postorder) {
3753
54+ // 第一步
3855 if (postorder.size() == 0) return NULL;
3956
40- // 后序遍历数组最后一个元素，就是当前的中间节点
57+ //第二步： 后序遍历数组最后一个元素，就是当前的中间节点
4158 int rootValue = postorder[postorder.size() - 1];
4259 TreeNode* root = new TreeNode(rootValue);
4360
4461 // 叶子节点
4562 if (postorder.size() == 1) return root;
4663
47- 找切割点
64+ // 第三步： 找切割点
4865 int delimiterIndex;
4966 for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {
5067 if (inorder[delimiterIndex] == rootValue) break;
5168 }
5269
53- 切割中序数组，得到 中序左数组和中序右数组
54- 切割后序数组，得到 后序左数组和后序右数组
70+ // 第四步： 切割中序数组，得到 中序左数组和中序右数组
71+ // 第五步： 切割后序数组，得到 后序左数组和后序右数组
5572
73+ // 第六步
5674 root->left = traversal(中序左数组, 后序左数组);
5775 root->right = traversal(中序右数组, 后序右数组);
5876
5977 return root;
6078 }
6179```
6280
63- 难点大家应该发现了，如何切割呢，边界值找不好很容易乱套。
81+ ** 难点大家应该发现了，就是如何切割，以及边界值找不好很容易乱套。 **
6482
6583此时应该注意确定切割的标准，是左闭右开，还有左开又闭，还是左闭又闭，这个就是不变量，要在递归中保持这个不变量。
6684
67- 在切割的过程中会产生四个区间，把握不好不变量的话，一会左闭右开，一会左闭又闭，必要乱套！
85+ ** 在切割的过程中会产生四个区间，把握不好不变量的话，一会左闭右开，一会左闭又闭，必然乱套！ **
6886
6987我在[ 数组：每次遇到二分法，都是一看就会，一写就废] ( https://mp.weixin.qq.com/s/fCf5QbPDtE6SSlZ1yh_q8Q ) 和[ 数组：这个循环可以转懵很多人！] ( https://mp.weixin.qq.com/s/KTPhaeqxbMK9CxHUUgFDmg ) 中都强调过循环不变量的重要性，在二分查找以及螺旋矩阵的求解中，坚持循环不变量非常重要，本题也是。
7088
@@ -77,17 +95,16 @@ https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorde
7795
7896
7997```
80- // 找到中序遍历的切割点
81- int delimiterIndex;
82- for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {
83- if (inorder[delimiterIndex] == rootValue) break;
84- }
85-
86- // 左闭右开区间
87- // [0, delimiterIndex)
88- vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
89- // [delimiterIndex + 1, end)
90- vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end() );
98+ // 找到中序遍历的切割点
99+ int delimiterIndex;
100+ for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {
101+ if (inorder[delimiterIndex] == rootValue) break;
102+ }
103+
104+ // 左闭右开区间：[0, delimiterIndex)
105+ vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
106+ // [delimiterIndex + 1, end)
107+ vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end() );
91108```
92109
93110接下来就要切割后序数组了。
@@ -96,7 +113,7 @@ https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorde
96113
97114后序数组的切割点怎么找？
98115
99- 后序数组没有明确的切割元素来进行左右切割，不想中序数组有明确的切割左右，左右分开就可以了 。
116+ 后序数组没有明确的切割元素来进行左右切割，不像中序数组有明确的切割点，切割点左右分开就可以了 。
100117
101118** 此时有一个很重的点，就是中序数组大小一定是和后序数组的大小相同的（这是必然）。**
102119
@@ -105,28 +122,27 @@ https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorde
105122代码如下：
106123
107124```
108-
109-
125+ // postorder 舍弃末尾元素，因为这个元素就是中间节点，已经用过了
126+ postorder.resize(postorder.size() - 1);
110127
111- // 依然左闭右开，注意这里使用了左中序数组大小作为切割点
112- // [0, leftInorder.size)
113- vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
114- // [leftInorder.size(), end)
115- vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());
128+ // 左闭右开，注意这里使用了左中序数组大小作为切割点：[0, leftInorder.size)
129+ vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
130+ // [leftInorder.size(), end)
131+ vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());
116132```
117133
118- 此时，中序数组切成了左中序数组和右中序数组，后序数组切割成序数组和右后序数组 。
134+ 此时，中序数组切成了左中序数组和右中序数组，后序数组切割成左后序数组和右后序数组 。
119135
120136接下来可以递归了，代码如下：
121137
122138```
123-
124-
139+ root->left = traversal(leftInorder, leftPostorder);
140+ root->right = traversal(rightInorder, rightPostorder);
125141```
126142
127143完整代码如下：
128144
129- ##C++
145+ ### C++完整代码
130146
131147```
132148class Solution {
@@ -206,6 +222,7 @@ private:
206222 vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
207223 vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());
208224
225+ // 一下为日志
209226 cout << "----------" << endl;
210227
211228 cout << "leftInorder :";
@@ -244,11 +261,11 @@ public:
244261};
245262```
246263
247- ** 此时应该发现了，如上的代码性能并不好，应为每层递归定定义了新的vector，既耗时又耗空间，但是上面的代码是最好理解的 ，为了方便读者理解，所以用如上的代码来讲解。**
264+ ** 此时应该发现了，如上的代码性能并不好，应为每层递归定定义了新的vector（就是数组） ，既耗时又耗空间，但上面的代码是最好理解的 ，为了方便读者理解，所以用如上的代码来讲解。**
248265
249266下面给出用下表索引写出的代码版本：（思路是一样的，只不过不用重复定义vector了，每次用下表索引来分割）
250267
251- ##C++最终优化版本
268+ ### C++优化版本
252269```
253270class Solution {
254271private:
@@ -368,7 +385,24 @@ public:
368385
369386#105. 从前序与中序遍历序列构造二叉树
370387
371- 同样的道理
388+ 根据一棵树的前序遍历与中序遍历构造二叉树。
389+
390+ 注意:
391+ 你可以假设树中没有重复的元素。
392+
393+ 例如，给出
394+
395+ 前序遍历 preorder = [ 3,9,20,15,7]
396+ 中序遍历 inorder =[ 9,3,15,20,7]
397+ 返回如下的二叉树：
398+
399+ <img src =' ../pics/105. 从前序与中序遍历序列构造二叉树.png ' width =600 > </img ></div >
400+
401+ ##思路
402+
403+ 本题和106是一样的道理。
404+
405+ 我就直接给出代码了。
372406
373407带日志的版本C++代码如下： （** 带日志的版本仅用于调试，不要在leetcode上提交，会超时** ）
374408
@@ -444,9 +478,8 @@ public:
444478};
445479```
446480
447- 105 .
481+ 105.从前序与中序遍历序列构造二叉树，最后版本，C++代码 ：
448482
449- C++代码：
450483```
451484class Solution {
452485private:
@@ -493,3 +526,45 @@ public:
493526 }
494527};
495528```
529+
530+ #思考题
531+
532+ 前序和中序可以唯一确定一颗二叉树。
533+
534+ 后序和中序可以唯一确定一颗二叉树。
535+
536+ 那么前序和后序可不可以唯一确定一颗二叉树呢？
537+
538+ ** 前序和后序不能唯一确定一颗二叉树！** ，因为没有中序遍历无法确定左右部分，也就是无法分割。
539+
540+ 举一个例子：
541+
542+ <img src =' ../pics/106.从中序与后序遍历序列构造二叉树2.png ' width =600 > </img ></div >
543+
544+ tree1 的前序遍历是[ 1 2 3] ， 后序遍历是[ 3 2 1] 。
545+
546+ tree2 的前序遍历是[ 1 2 3] ， 后序遍历是[ 3 2 1] 。
547+
548+ 那么tree1 和 tree2 的前序和后序完全相同，这是一棵树么，很明显是两棵树！
549+
550+ 所以前序和后序不能唯一确定一颗二叉树！
551+
552+ #总结
553+
554+ 之前我们讲的二叉树题目都是各种遍历二叉树，这次开始构造二叉树了，思路其实比较简单，但是真正代码实现出来并不容易。
555+
556+ 所以要避免眼高手低，踏实的把代码写出来。
557+
558+ 我同时给出了添加日志的代码版本，因为这种题目是不太容易写出来调一调就能过的，所以一定要把流程日志打出来，看看符不符合自己的思路。
559+
560+ 大家遇到这种题目的时候，也要学会打日志来调试（如何打日志有时候也是个技术活），不要脑动模拟，脑动模拟很容易越想越乱。
561+
562+ 最后我还给出了为什么前序和中序可以唯一确定一颗二叉树，后序和中序可以唯一确定一颗二叉树，而前序和后序却不行。
563+
564+ 认真研究完本篇，相信大家对二叉树的构造会清晰很多。
565+
566+ 如果学到了，就赶紧转发给身边需要的同学吧！
567+
568+ 加个油！
569+
570+