排序⼆叉树的中序遍历序列是有序序列_「leetcode」106.从中序与后序遍历序列构造⼆。。。
106.从中序与后序遍历序列构造⼆叉树
根据⼀棵树的中序遍历与后序遍历构造⼆叉树。
注意: 你可以假设树中没有重复的元素。
例如，给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的⼆叉树：
思路
⾸先回忆⼀下如何根据两个顺序构造⼀个唯⼀的⼆叉树，相信理论知识⼤家应该都清楚，就是以 后序数组的最后⼀个元素为切割点，先切中序数组，根据中序数组，反过来在切后序数组。⼀层⼀层切下去，每次后序数组最后⼀个元素就是节点元素。
如果让我们⾁眼看两个序列，画⼀颗⼆叉树的话，应该分分钟都可以画出来。
流程如图：
那么代码应该怎么写呢？
说到⼀层⼀层切割，就应该想到了递归。
来看⼀下⼀共分⼏步：
第⼀步：如果数组⼤⼩为零的话，说明是空节点了。
第⼆步：如果不为空，那么取后序数组最后⼀个元素作为节点元素。
第三步：到后序数组最后⼀个元素在中序数组的位置，作为切割点
第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，⼀定是先切中序数组）
第五步：切割后序数组，切成后序左数组和后序右数组
第六步：递归处理左区间和右区间
不难写出如下代码：（先把框架写出来）
TreeNode* traversal (vector<int>& inorder, vector<int>& postorder) {
/
/ 第⼀步
if (postorder.size() == 0) return NULL;
// 第⼆步：后序遍历数组最后⼀个元素，就是当前的中间节点
int rootValue = postorder[postorder.size() - 1];
TreeNode* root = new TreeNode(rootValue);
// 叶⼦节点
if (postorder.size() == 1) return root;
// 第三步：切割点
int delimiterIndex;
for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {
if (inorder[delimiterIndex] == rootValue) break;
}
// 第四步：切割中序数组，得到中序左数组和中序右数组
// 第五步：切割后序数组，得到后序左数组和后序右数组
// 第六步
root->left = traversal(中序左数组, 后序左数组);
root->right = traversal(中序右数组, 后序右数组);
return root;
}
「难点⼤家应该发现了，就是如何切割，以及边界值不好很容易乱套。」
此时应该注意确定切割的标准，是左闭右开，还有左开⼜闭，还是左闭⼜闭，这个就是不变量，要在递归中保持这个不变量。
「在切割的过程中会产⽣四个区间，把握不好不变量的话，⼀会左闭右开，⼀会左闭⼜闭，必然乱套！」
我在数组：每次遇到⼆分法，都是⼀看就会，⼀写就废和数组：这个循环可以转懵很多⼈！中都强调过循环不变量的重要性，在⼆分查以及螺旋矩阵的求解中，坚持循环不变量⾮常重要，本题也是。
先序中序后序遍历二叉树
⾸先要切割中序数组，为什么先切割中序数组呢？
切割点在后序数组的最后⼀个元素，就是⽤这个元素来切割中序数组的，所以必要先切割中序数组。
中序数组相对⽐较好切，到切割点（后序数组的最后⼀个元素）在中序数组的位置，然后切割，如下代码中我坚持左闭右开的原则：
// 到中序遍历的切割点
int delimiterIndex;
for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {
if (inorder[delimiterIndex] == rootValue) break;
}
// 左闭右开区间：[0, delimiterIndex)
vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
// [delimiterIndex + 1, end)
vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, d() );
接下来就要切割后序数组了。
⾸先后序数组的最后⼀个元素指定不能要了，这是切割点 也是 当前⼆叉树中间节点的元素，已经⽤了。
后序数组的切割点怎么？
后序数组没有明确的切割元素来进⾏左右切割，不像中序数组有明确的切割点，切割点左右分开就可以了。
「此时有⼀个很重的点，就是中序数组⼤⼩⼀定是和后序数组的⼤⼩相同的（这是必然）。」
中序数组我们都切成了左中序数组和右中序数组了，那么后序数组就可以按照左中序数组的⼤⼩来切割，切成左后序数组和右后序数组。代码如下：
// postorder 舍弃末尾元素，因为这个元素就是中间节点，已经⽤过了
// 左闭右开，注意这⾥使⽤了左中序数组⼤⼩作为切割点：[0, leftInorder.size)
vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
// [leftInorder.size(), end)
vector<int> rightPostorder(postorder.begin() + leftInorder.size(), d());
此时，中序数组切成了左中序数组和右中序数组，后序数组切割成左后序数组和右后序数组。
接下来可以递归了，代码如下：
root->left = traversal(leftInorder, leftPostorder);
root->right = traversal(rightInorder, rightPostorder);
完整代码如下：
C++完整代码
// 后序遍历数组最后⼀个元素，就是当前的中间节点
int rootValue = postorder[postorder.size() - 1];
TreeNode* root = new TreeNode(rootValue);
// 叶⼦节点
if (postorder.size() == 1) return root;
// 到中序遍历的切割点
int delimiterIndex;
for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {
if (inorder[delimiterIndex] == rootValue) break;
}
// 切割中序数组
// 左闭右开区间：[0, delimiterIndex)
vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
// [delimiterIndex + 1, end)
vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, d() );
// postorder 舍弃末尾元素
// 切割后序数组
// 依然左闭右开，注意这⾥使⽤了左中序数组⼤⼩作为切割点
// [0, leftInorder.size)
vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
// [leftInorder.size(), end)
vector<int> rightPostorder(postorder.begin() + leftInorder.size(), d());
root->left = traversal(leftInorder, leftPostorder);
root->right = traversal(rightInorder, rightPostorder);
return root;
}
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if (inorder.size() == 0 || postorder.size() == 0) return NULL;
return traversal(inorder, postorder);
}
};
相信⼤家⾃⼰就算是思路清晰， 代码写出来⼀定是各种问题，所以⼀定要加⽇志来调试，看看是不是按照⾃⼰思路来切割的，不要⼤脑模拟，那样越想越糊涂。
加了⽇志的代码如下：（加了⽇志的代码不要在leetcode上提交，容易超时）
int rootValue = postorder[postorder.size() - 1];
TreeNode* root = new TreeNode(rootValue);
if (postorder.size() == 1) return root;
int delimiterIndex;
for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {
if (inorder[delimiterIndex] == rootValue) break;
}
vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, d() );
vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
vector<int> rightPostorder(postorder.begin() + leftInorder.size(), d());
// 以下为⽇志
cout << "----------" << endl;
cout << "leftInorder :";
for (int i : leftInorder) {
cout << i << " ";
}
cout << endl;
cout << "rightInorder :";
for (int i : rightInorder) {
cout << i << " ";
}
cout << endl;
cout << "leftPostorder :";
for (int i : leftPostorder) {
cout << i << " ";
}
cout << endl;
cout << "rightPostorder :";
for (int i : rightPostorder) {
cout << i << " ";
}
cout << endl;
root->left = traversal(leftInorder, leftPostorder);
root->right = traversal(rightInorder, rightPostorder);
return root;
}
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if (inorder.size() == 0 || postorder.size() == 0) return NULL;
return traversal(inorder, postorder);
}
};
「此时应该发现了，如上的代码性能并不好，应为每层递归定定义了新的vector（就是数组），既耗时⼜耗空间，但上⾯的代码是最好理解的，为了⽅便读者理解，所以⽤如上的代码来讲解。」

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。