参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们受益！
看完本文，可以一起解决如下两道题目
- 106.从中序与后序遍历序列构造二叉树
- 105.从前序与中序遍历序列构造二叉树
根据一棵树的中序遍历与后序遍历构造二叉树。
注意: 你可以假设树中没有重复的元素。
例如，给出
- 中序遍历 inorder = [9,3,15,20,7]
- 后序遍历 postorder = [9,15,7,20,3] 返回如下的二叉树：
《代码随想录》算法视频公开课：坑很多！来看看你掉过几次坑 | LeetCode：106.从中序与后序遍历序列构造二叉树，相信结合视频在看本篇题解，更有助于大家对本题的理解。
首先回忆一下如何根据两个顺序构造一个唯一的二叉树，相信理论知识大家应该都清楚，就是以 后序数组的最后一个元素为切割点，先切中序数组，根据中序数组，反过来再切后序数组。一层一层切下去，每次后序数组最后一个元素就是节点元素。
如果让我们肉眼看两个序列，画一棵二叉树的话，应该分分钟都可以画出来。
流程如图：
那么代码应该怎么写呢？
说到一层一层切割，就应该想到了递归。
来看一下一共分几步：
-
第一步：如果数组大小为零的话，说明是空节点了。
-
第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。
-
第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点
-
第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）
-
第五步：切割后序数组，切成后序左数组和后序右数组
-
第六步：递归处理左区间和右区间
不难写出如下代码：（先把框架写出来）
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, inorder.end() );接下来就要切割后序数组了。
首先后序数组的最后一个元素指定不能要了，这是切割点 也是 当前二叉树中间节点的元素，已经用了。
后序数组的切割点怎么找？
后序数组没有明确的切割元素来进行左右切割，不像中序数组有明确的切割点，切割点左右分开就可以了。
此时有一个很重的点，就是中序数组大小一定是和后序数组的大小相同的（这是必然）。
中序数组我们都切成了左中序数组和右中序数组了，那么后序数组就可以按照左中序数组的大小来切割，切成左后序数组和右后序数组。
代码如下：
// postorder 舍弃末尾元素，因为这个元素就是中间节点，已经用过了
postorder.resize(postorder.size() - 1);
// 左闭右开，注意这里使用了左中序数组大小作为切割点：[0, leftInorder.size)
vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
// [leftInorder.size(), end)
vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());此时，中序数组切成了左中序数组和右中序数组，后序数组切割成左后序数组和右后序数组。
接下来可以递归了，代码如下：
root->left = traversal(leftInorder, leftPostorder);
root->right = traversal(rightInorder, rightPostorder);完整代码如下：
class Solution {
private:
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;
}
// 切割中序数组
// 左闭右开区间：[0, delimiterIndex)
vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
// [delimiterIndex + 1, end)
vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end() );
// postorder 舍弃末尾元素
postorder.resize(postorder.size() - 1);
// 切割后序数组
// 依然左闭右开，注意这里使用了左中序数组大小作为切割点
// [0, leftInorder.size)
vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
// [leftInorder.size(), end)
vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());
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上提交，容易超时）
class Solution {
private:
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;
}
vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end() );
postorder.resize(postorder.size() - 1);
vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());
// 以下为日志
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（就是数组），既耗时又耗空间，但上面的代码是最好理解的，为了方便读者理解，所以用如上的代码来讲解。
下面给出用下标索引写出的代码版本：（思路是一样的，只不过不用重复定义vector了，每次用下标索引来分割）
class Solution {
private:
// 中序区间：[inorderBegin, inorderEnd)，后序区间[postorderBegin, postorderEnd)
TreeNode* traversal (vector<int>& inorder, int inorderBegin, int inorderEnd, vector<int>& postorder, int postorderBegin, int postorderEnd) {
if (postorderBegin == postorderEnd) return NULL;
int rootValue = postorder[postorderEnd - 1];
TreeNode* root = new TreeNode(rootValue);
if (postorderEnd - postorderBegin == 1) return root;
int delimiterIndex;
for (delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) {
if (inorder[delimiterIndex] == rootValue) break;
}
// 切割中序数组
// 左中序区间，左闭右开[leftInorderBegin, leftInorderEnd)
int leftInorderBegin = inorderBegin;
int leftInorderEnd = delimiterIndex;
// 右中序区间，左闭右开[rightInorderBegin, rightInorderEnd)
int rightInorderBegin = delimiterIndex + 1;
int rightInorderEnd = inorderEnd;
// 切割后序数组
// 左后序区间，左闭右开[leftPostorderBegin, leftPostorderEnd)
int leftPostorderBegin = postorderBegin;
int leftPostorderEnd = postorderBegin + delimiterIndex - inorderBegin; // 终止位置是 需要加上 中序区间的大小size
// 右后序区间，左闭右开[rightPostorderBegin, rightPostorderEnd)
int rightPostorderBegin = postorderBegin + (delimiterIndex - inorderBegin);
int rightPostorderEnd = postorderEnd - 1; // 排除最后一个元素，已经作为节点了
root->left = traversal(inorder, leftInorderBegin, leftInorderEnd, postorder, leftPostorderBegin, leftPostorderEnd);
root->right = traversal(inorder, rightInorderBegin, rightInorderEnd, postorder, rightPostorderBegin, rightPostorderEnd);
return root;
}
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if (inorder.size() == 0 || postorder.size() == 0) return NULL;
// 左闭右开的原则
return traversal(inorder, 0, inorder.size(), postorder, 0, postorder.size());
}
};那么这个版本写出来依然要打日志进行调试，打日志的版本如下：（该版本不要在leetcode上提交，容易超时）
class Solution {
private:
TreeNode* traversal (vector<int>& inorder, int inorderBegin, int inorderEnd, vector<int>& postorder, int postorderBegin, int postorderEnd) {
if (postorderBegin == postorderEnd) return NULL;
int rootValue = postorder[postorderEnd - 1];
TreeNode* root = new TreeNode(rootValue);
if (postorderEnd - postorderBegin == 1) return root;
int delimiterIndex;
for (delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) {
if (inorder[delimiterIndex] == rootValue) break;
}
// 切割中序数组
// 左中序区间，左闭右开[leftInorderBegin, leftInorderEnd)
int leftInorderBegin = inorderBegin;
int leftInorderEnd = delimiterIndex;
// 右中序区间，左闭右开[rightInorderBegin, rightInorderEnd)
int rightInorderBegin = delimiterIndex + 1;
int rightInorderEnd = inorderEnd;
// 切割后序数组
// 左后序区间，左闭右开[leftPostorderBegin, leftPostorderEnd)
int leftPostorderBegin = postorderBegin;
int leftPostorderEnd = postorderBegin + delimiterIndex - inorderBegin; // 终止位置是 需要加上 中序区间的大小size
// 右后序区间，左闭右开[rightPostorderBegin, rightPostorderEnd)
int rightPostorderBegin = postorderBegin + (delimiterIndex - inorderBegin);
int rightPostorderEnd = postorderEnd - 1; // 排除最后一个元素，已经作为节点了
cout << "----------" << endl;
cout << "leftInorder :";
for (int i = leftInorderBegin; i < leftInorderEnd; i++) {
cout << inorder[i] << " ";
}
cout << endl;
cout << "rightInorder :";
for (int i = rightInorderBegin; i < rightInorderEnd; i++) {
cout << inorder[i] << " ";
}
cout << endl;
cout << "leftpostorder :";
for (int i = leftPostorderBegin; i < leftPostorderEnd; i++) {
cout << postorder[i] << " ";
}
cout << endl;
cout << "rightpostorder :";
for (int i = rightPostorderBegin; i < rightPostorderEnd; i++) {
cout << postorder[i] << " ";
}
cout << endl;
root->left = traversal(inorder, leftInorderBegin, leftInorderEnd, postorder, leftPostorderBegin, leftPostorderEnd);
root->right = traversal(inorder, rightInorderBegin, rightInorderEnd, postorder, rightPostorderBegin, rightPostorderEnd);
return root;
}
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if (inorder.size() == 0 || postorder.size() == 0) return NULL;
return traversal(inorder, 0, inorder.size(), postorder, 0, postorder.size());
}
};根据一棵树的前序遍历与中序遍历构造二叉树。
注意: 你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树：
本题和106是一样的道理。
我就直接给出代码了。
带日志的版本C++代码如下： （带日志的版本仅用于调试，不要在leetcode上提交，会超时）
class Solution {
private:
TreeNode* traversal (vector<int>& inorder, int inorderBegin, int inorderEnd, vector<int>& preorder, int preorderBegin, int preorderEnd) {
if (preorderBegin == preorderEnd) return NULL;
int rootValue = preorder[preorderBegin]; // 注意用preorderBegin 不要用0
TreeNode* root = new TreeNode(rootValue);
if (preorderEnd - preorderBegin == 1) return root;
int delimiterIndex;
for (delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) {
if (inorder[delimiterIndex] == rootValue) break;
}
// 切割中序数组
// 中序左区间，左闭右开[leftInorderBegin, leftInorderEnd)
int leftInorderBegin = inorderBegin;
int leftInorderEnd = delimiterIndex;
// 中序右区间，左闭右开[rightInorderBegin, rightInorderEnd)
int rightInorderBegin = delimiterIndex + 1;
int rightInorderEnd = inorderEnd;
// 切割前序数组
// 前序左区间，左闭右开[leftPreorderBegin, leftPreorderEnd)
int leftPreorderBegin = preorderBegin + 1;
int leftPreorderEnd = preorderBegin + 1 + delimiterIndex - inorderBegin; // 终止位置是起始位置加上中序左区间的大小size
// 前序右区间, 左闭右开[rightPreorderBegin, rightPreorderEnd)
int rightPreorderBegin = preorderBegin + 1 + (delimiterIndex - inorderBegin);
int rightPreorderEnd = preorderEnd;
cout << "----------" << endl;
cout << "leftInorder :";
for (int i = leftInorderBegin; i < leftInorderEnd; i++) {
cout << inorder[i] << " ";
}
cout << endl;
cout << "rightInorder :";
for (int i = rightInorderBegin; i < rightInorderEnd; i++) {
cout << inorder[i] << " ";
}
cout << endl;
cout << "leftPreorder :";
for (int i = leftPreorderBegin; i < leftPreorderEnd; i++) {
cout << preorder[i] << " ";
}
cout << endl;
cout << "rightPreorder :";
for (int i = rightPreorderBegin; i < rightPreorderEnd; i++) {
cout << preorder[i] << " ";
}
cout << endl;
root->left = traversal(inorder, leftInorderBegin, leftInorderEnd, preorder, leftPreorderBegin, leftPreorderEnd);
root->right = traversal(inorder, rightInorderBegin, rightInorderEnd, preorder, rightPreorderBegin, rightPreorderEnd);
return root;
}
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if (inorder.size() == 0 || preorder.size() == 0) return NULL;
return traversal(inorder, 0, inorder.size(), preorder, 0, preorder.size());
}
};105.从前序与中序遍历序列构造二叉树，最后版本，C++代码：
class Solution {
private:
TreeNode* traversal (vector<int>& inorder, int inorderBegin, int inorderEnd, vector<int>& preorder, int preorderBegin, int preorderEnd) {
if (preorderBegin == preorderEnd) return NULL;
int rootValue = preorder[preorderBegin]; // 注意用preorderBegin 不要用0
TreeNode* root = new TreeNode(rootValue);
if (preorderEnd - preorderBegin == 1) return root;
int delimiterIndex;
for (delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) {
if (inorder[delimiterIndex] == rootValue) break;
}
// 切割中序数组
// 中序左区间，左闭右开[leftInorderBegin, leftInorderEnd)
int leftInorderBegin = inorderBegin;
int leftInorderEnd = delimiterIndex;
// 中序右区间，左闭右开[rightInorderBegin, rightInorderEnd)
int rightInorderBegin = delimiterIndex + 1;
int rightInorderEnd = inorderEnd;
// 切割前序数组
// 前序左区间，左闭右开[leftPreorderBegin, leftPreorderEnd)
int leftPreorderBegin = preorderBegin + 1;
int leftPreorderEnd = preorderBegin + 1 + delimiterIndex - inorderBegin; // 终止位置是起始位置加上中序左区间的大小size
// 前序右区间, 左闭右开[rightPreorderBegin, rightPreorderEnd)
int rightPreorderBegin = preorderBegin + 1 + (delimiterIndex - inorderBegin);
int rightPreorderEnd = preorderEnd;
root->left = traversal(inorder, leftInorderBegin, leftInorderEnd, preorder, leftPreorderBegin, leftPreorderEnd);
root->right = traversal(inorder, rightInorderBegin, rightInorderEnd, preorder, rightPreorderBegin, rightPreorderEnd);
return root;
}
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if (inorder.size() == 0 || preorder.size() == 0) return NULL;
// 参数坚持左闭右开的原则
return traversal(inorder, 0, inorder.size(), preorder, 0, preorder.size());
}
};前序和中序可以唯一确定一棵二叉树。
后序和中序可以唯一确定一棵二叉树。
那么前序和后序可不可以唯一确定一棵二叉树呢？
前序和后序不能唯一确定一棵二叉树！，因为没有中序遍历无法确定左右部分，也就是无法分割。
举一个例子：
tree1 的前序遍历是[1 2 3]， 后序遍历是[3 2 1]。
tree2 的前序遍历是[1 2 3]， 后序遍历是[3 2 1]。
那么tree1 和 tree2 的前序和后序完全相同，这是一棵树么，很明显是两棵树！
所以前序和后序不能唯一确定一棵二叉树！
之前我们讲的二叉树题目都是各种遍历二叉树，这次开始构造二叉树了，思路其实比较简单，但是真正代码实现出来并不容易。
所以要避免眼高手低，踏实地把代码写出来。
我同时给出了添加日志的代码版本，因为这种题目是不太容易写出来调一调就能过的，所以一定要把流程日志打出来，看看符不符合自己的思路。
大家遇到这种题目的时候，也要学会打日志来调试（如何打日志有时候也是个技术活），不要脑动模拟，脑动模拟很容易越想越乱。
最后我还给出了为什么前序和中序可以唯一确定一棵二叉树，后序和中序可以唯一确定一棵二叉树，而前序和后序却不行。
认真研究完本篇，相信大家对二叉树的构造会清晰很多。
106.从中序与后序遍历序列构造二叉树
class Solution {
Map<Integer, Integer> map; // 方便根据数值查找位置
public TreeNode buildTree(int[] inorder, int[] postorder) {
map = new HashMap<>();
for (int i = 0; i < inorder.length; i++) { // 用map保存中序序列的数值对应位置
map.put(inorder[i], i);
}
return findNode(inorder, 0, inorder.length, postorder,0, postorder.length); // 前闭后开
}
public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) {
// 参数里的范围都是前闭后开
if (inBegin >= inEnd || postBegin >= postEnd) { // 不满足左闭右开，说明没有元素，返回空树
return null;
}
int rootIndex = map.get(postorder[postEnd - 1]); // 找到后序遍历的最后一个元素在中序遍历中的位置
TreeNode root = new TreeNode(inorder[rootIndex]); // 构造结点
int lenOfLeft = rootIndex - inBegin; // 保存中序左子树个数，用来确定后序数列的个数
root.left = findNode(inorder, inBegin, rootIndex,
postorder, postBegin, postBegin + lenOfLeft);
root.right = findNode(inorder, rootIndex + 1, inEnd,
postorder, postBegin + lenOfLeft, postEnd - 1);
return root;
}
}class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
if(postorder.length == 0 || inorder.length == 0)
return null;
return buildHelper(inorder, 0, inorder.length, postorder, 0, postorder.length);
}
private TreeNode buildHelper(int[] inorder, int inorderStart, int inorderEnd, int[] postorder, int postorderStart, int postorderEnd){
if(postorderStart == postorderEnd)
return null;
int rootVal = postorder[postorderEnd - 1];
TreeNode root = new TreeNode(rootVal);
int middleIndex;
for (middleIndex = inorderStart; middleIndex < inorderEnd; middleIndex++){
if(inorder[middleIndex] == rootVal)
break;
}
int leftInorderStart = inorderStart;
int leftInorderEnd = middleIndex;
int rightInorderStart = middleIndex + 1;
int rightInorderEnd = inorderEnd;
int leftPostorderStart = postorderStart;
int leftPostorderEnd = postorderStart + (middleIndex - inorderStart);
int rightPostorderStart = leftPostorderEnd;
int rightPostorderEnd = postorderEnd - 1;
root.left = buildHelper(inorder, leftInorderStart, leftInorderEnd, postorder, leftPostorderStart, leftPostorderEnd);
root.right = buildHelper(inorder, rightInorderStart, rightInorderEnd, postorder, rightPostorderStart, rightPostorderEnd);
return root;
}
}105.从前序与中序遍历序列构造二叉树
class Solution {
Map<Integer, Integer> map;
public TreeNode buildTree(int[] preorder, int[] inorder) {
map = new HashMap<>();
for (int i = 0; i < inorder.length; i++) { // 用map保存中序序列的数值对应位置
map.put(inorder[i], i);
}
return findNode(preorder, 0, preorder.length, inorder, 0, inorder.length); // 前闭后开
}
public TreeNode findNode(int[] preorder, int preBegin, int preEnd, int[] inorder, int inBegin, int inEnd) {
// 参数里的范围都是前闭后开
if (preBegin >= preEnd || inBegin >= inEnd) { // 不满足左闭右开，说明没有元素，返回空树
return null;
}
int rootIndex = map.get(preorder[preBegin]); // 找到前序遍历的第一个元素在中序遍历中的位置
TreeNode root = new TreeNode(inorder[rootIndex]); // 构造结点
int lenOfLeft = rootIndex - inBegin; // 保存中序左子树个数，用来确定前序数列的个数
root.left = findNode(preorder, preBegin + 1, preBegin + lenOfLeft + 1,
inorder, inBegin, rootIndex);
root.right = findNode(preorder, preBegin + lenOfLeft + 1, preEnd,
inorder, rootIndex + 1, inEnd);
return root;
}
}105.从前序与中序遍历序列构造二叉树
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
# 第一步: 特殊情况讨论: 树为空. 或者说是递归终止条件
if not preorder:
return None
# 第二步: 前序遍历的第一个就是当前的中间节点.
root_val = preorder[0]
root = TreeNode(root_val)
# 第三步: 找切割点.
separator_idx = inorder.index(root_val)
# 第四步: 切割inorder数组. 得到inorder数组的左,右半边.
inorder_left = inorder[:separator_idx]
inorder_right = inorder[separator_idx + 1:]
# 第五步: 切割preorder数组. 得到preorder数组的左,右半边.
# ⭐️ 重点1: 中序数组大小一定跟前序数组大小是相同的.
preorder_left = preorder[1:1 + len(inorder_left)]
preorder_right = preorder[1 + len(inorder_left):]
# 第六步: 递归
root.left = self.buildTree(preorder_left, inorder_left)
root.right = self.buildTree(preorder_right, inorder_right)
# 第七步: 返回答案
return root106.从中序与后序遍历序列构造二叉树
class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
# 第一步: 特殊情况讨论: 树为空. (递归终止条件)
if not postorder:
return None
# 第二步: 后序遍历的最后一个就是当前的中间节点.
root_val = postorder[-1]
root = TreeNode(root_val)
# 第三步: 找切割点.
separator_idx = inorder.index(root_val)
# 第四步: 切割inorder数组. 得到inorder数组的左,右半边.
inorder_left = inorder[:separator_idx]
inorder_right = inorder[separator_idx + 1:]
# 第五步: 切割postorder数组. 得到postorder数组的左,右半边.
# ⭐️ 重点1: 中序数组大小一定跟后序数组大小是相同的.
postorder_left = postorder[:len(inorder_left)]
postorder_right = postorder[len(inorder_left): len(postorder) - 1]
# 第六步: 递归
root.left = self.buildTree(inorder_left, postorder_left)
root.right = self.buildTree(inorder_right, postorder_right)
# 第七步: 返回答案
return root106 从中序与后序遍历序列构造二叉树
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
var (
hash map[int]int
)
func buildTree(inorder []int, postorder []int) *TreeNode {
hash = make(map[int]int)
for i, v := range inorder { // 用map保存中序序列的数值对应位置
hash[v] = i
}
// 以左闭右闭的原则进行切分
root := rebuild(inorder, postorder, len(postorder)-1, 0, len(inorder)-1)
return root
}
// rootIdx表示根节点在后序数组中的索引，l, r 表示在中序数组中的前后切分点
func rebuild(inorder []int, postorder []int, rootIdx int, l, r int) *TreeNode {
if l > r { // 说明没有元素，返回空树
return nil
}
if l == r { // 只剩唯一一个元素，直接返回
return &TreeNode{Val : inorder[l]}
}
rootV := postorder[rootIdx] // 根据后序数组找到根节点的值
rootIn := hash[rootV] // 找到根节点在对应的中序数组中的位置
root := &TreeNode{Val : rootV} // 构造根节点
// 重建左节点和右节点
root.Left = rebuild(inorder, postorder, rootIdx-(r-rootIn)-1, l, rootIn-1)
root.Right = rebuild(inorder, postorder, rootIdx-1, rootIn+1, r)
return root
}105 从前序与中序遍历序列构造二叉树
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
var (
hash map[int]int
)
func buildTree(preorder []int, inorder []int) *TreeNode {
hash = make(map[int]int, len(inorder))
for i, v := range inorder {
hash[v] = i
}
root := build(preorder, inorder, 0, 0, len(inorder)-1) // l, r 表示构造的树在中序遍历数组中的范围
return root
}
func build(pre []int, in []int, root int, l, r int) *TreeNode {
if l > r {
return nil
}
rootVal := pre[root] // 找到本次构造的树的根节点
index := hash[rootVal] // 根节点在中序数组中的位置
node := &TreeNode {Val: rootVal}
node.Left = build(pre, in, root + 1, l, index-1)
node.Right = build(pre, in, root + (index-l) + 1, index+1, r)
return node
}var buildTree = function(inorder, postorder) {
if (!inorder.length) return null;
const rootVal = postorder.pop(); // 从后序遍历的数组中获取中间节点的值， 即数组最后一个值
let rootIndex = inorder.indexOf(rootVal); // 获取中间节点在中序遍历中的下标
const root = new TreeNode(rootVal); // 创建中间节点
root.left = buildTree(inorder.slice(0, rootIndex), postorder.slice(0, rootIndex)); // 创建左节点
root.right = buildTree(inorder.slice(rootIndex + 1), postorder.slice(rootIndex)); // 创建右节点
return root;
};从前序与中序遍历序列构造二叉树
var buildTree = function(preorder, inorder) {
if (!preorder.length) return null;
const rootVal = preorder.shift(); // 从前序遍历的数组中获取中间节点的值， 即数组第一个值
const index = inorder.indexOf(rootVal); // 获取中间节点在中序遍历中的下标
const root = new TreeNode(rootVal); // 创建中间节点
root.left = buildTree(preorder.slice(0, index), inorder.slice(0, index)); // 创建左节点
root.right = buildTree(preorder.slice(index), inorder.slice(index + 1)); // 创建右节点
return root;
};106.从中序与后序遍历序列构造二叉树
创建新数组:
function buildTree(inorder: number[], postorder: number[]): TreeNode | null {
if (postorder.length === 0) return null;
const rootVal: number = postorder.pop()!;
const rootValIndex: number = inorder.indexOf(rootVal);
const rootNode: TreeNode = new TreeNode(rootVal);
rootNode.left = buildTree(inorder.slice(0, rootValIndex), postorder.slice(0, rootValIndex));
rootNode.right = buildTree(inorder.slice(rootValIndex + 1), postorder.slice(rootValIndex));
return rootNode;
};使用数组索引:
function buildTree(inorder: number[], postorder: number[]): TreeNode | null {
function recur(
inorder: number[], postorder: number[],
inBegin: number, inEnd: number,
postBegin: number, postEnd: number
): TreeNode | null {
if (postBegin === postEnd) return null;
const rootVal: number = postorder[postEnd - 1]!;
const rootValIndex: number = inorder.indexOf(rootVal, inBegin);
const rootNode: TreeNode = new TreeNode(rootVal);
const leftInorderBegin: number = inBegin;
const leftInorderEnd: number = rootValIndex;
const rightInorderBegin: number = rootValIndex + 1;
const rightInorderEnd: number = inEnd;
const leftPostorderBegin: number = postBegin;
const leftPostorderEnd: number = postBegin + rootValIndex - inBegin;
const rightPostorderBegin: number = leftPostorderEnd;
const rightPostorderEnd: number = postEnd - 1;
rootNode.left = recur(
inorder, postorder,
leftInorderBegin, leftInorderEnd,
leftPostorderBegin, leftPostorderEnd
);
rootNode.right = recur(
inorder, postorder,
rightInorderBegin, rightInorderEnd,
rightPostorderBegin, rightPostorderEnd
);
return rootNode;
}
return recur(inorder, postorder, 0, inorder.length, 0, inorder.length);
};105.从前序与中序遍历序列构造二叉树
新建数组：
function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
if (preorder.length === 0) return null;
const rootVal: number = preorder[0];
const rootNode: TreeNode = new TreeNode(rootVal);
const rootValIndex: number = inorder.indexOf(rootVal);
rootNode.left = buildTree(preorder.slice(1, rootValIndex + 1), inorder.slice(0, rootValIndex));
rootNode.right = buildTree(preorder.slice(rootValIndex + 1), inorder.slice(rootValIndex + 1));
return rootNode;
};使用数组索引:
function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
function recur(
preorder: number[], inorder: number[],
preBegin: number, preEnd: number,
inBegin: number, inEnd: number
): TreeNode | null {
if (preBegin === preEnd) return null;
const rootVal: number = preorder[preBegin];
const rootNode: TreeNode = new TreeNode(rootVal);
const rootValIndex: number = inorder.indexOf(rootVal, inBegin);
const leftPreBegin: number = preBegin + 1;
const leftPreEnd: number = preBegin + rootValIndex - inBegin + 1;
const leftInBegin: number = inBegin;
const leftInEnd: number = rootValIndex;
const rightPreBegin: number = leftPreEnd;
const rightPreEnd: number = preEnd;
const rightInBegin: number = rootValIndex + 1;
const rightInEnd: number = inEnd;
rootNode.left = recur(preorder, inorder, leftPreBegin, leftPreEnd, leftInBegin, leftInEnd);
rootNode.right = recur(preorder, inorder, rightPreBegin, rightPreEnd, rightInBegin, rightInEnd);
return rootNode;
};
return recur(preorder, inorder, 0, preorder.length, 0, inorder.length);
};106 从中序与后序遍历序列构造二叉树
int linearSearch(int* arr, int arrSize, int key) {
int i;
for(i = 0; i < arrSize; i++) {
if(arr[i] == key)
return i;
}
return -1;
}
struct TreeNode* buildTree(int* inorder, int inorderSize, int* postorder, int postorderSize){
//若中序遍历数组中没有元素，则返回NULL
if(!inorderSize)
return NULL;
//创建一个新的结点，将node的val设置为后序遍历的最后一个元素
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->val = postorder[postorderSize - 1];
//通过线性查找找到中间结点在中序数组中的位置
int index = linearSearch(inorder, inorderSize, postorder[postorderSize - 1]);
//左子树数组大小为index
//右子树的数组大小为数组大小减index减1（减的1为中间结点）
int rightSize = inorderSize - index - 1;
node->left = buildTree(inorder, index, postorder, index);
node->right = buildTree(inorder + index + 1, rightSize, postorder + index, rightSize);
return node;
}105 从前序与中序遍历序列构造二叉树
struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize){
// 递归结束条件：传入的数组大小为0
if(!preorderSize)
return NULL;
// 1.找到前序遍历数组的第一个元素， 创建结点。左右孩子设置为NULL。
int rootValue = preorder[0];
struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->val = rootValue;
root->left = NULL;
root->right = NULL;
// 2.若前序遍历数组的大小为1，返回该结点
if(preorderSize == 1)
return root;
// 3.根据该结点切割中序遍历数组，将中序遍历数组分割成左右两个数组。算出他们的各自大小
int index;
for(index = 0; index < inorderSize; index++) {
if(inorder[index] == rootValue)
break;
}
int leftNum = index;
int rightNum = inorderSize - index - 1;
int* leftInorder = inorder;
int* rightInorder = inorder + leftNum + 1;
// 4.根据中序遍历数组左右数组的各子大小切割前序遍历数组。也分为左右数组
int* leftPreorder = preorder+1;
int* rightPreorder = preorder + 1 + leftNum;
// 5.递归进入左右数组，将返回的结果作为根结点的左右孩子
root->left = buildTree(leftPreorder, leftNum, leftInorder, leftNum);
root->right = buildTree(rightPreorder, rightNum, rightInorder, rightNum);
// 6.返回根节点
return root;
}105 从前序与中序遍历序列构造二叉树
class Solution {
func buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
return helper(preorder: preorder,
preorderBegin: 0,
preorderEnd: preorder.count,
inorder: inorder,
inorderBegin: 0,
inorderEnd: inorder.count)
}
func helper(preorder: [Int], preorderBegin: Int, preorderEnd: Int, inorder: [Int], inorderBegin: Int, inorderEnd: Int) -> TreeNode? {
if preorderBegin == preorderEnd {
return nil
}
// 前序遍历数组的第一个元素作为分割点
let rootValue = preorder[preorderBegin]
let root = TreeNode(rootValue)
if preorderEnd - preorderBegin == 1 {
return root
}
var index = 0 // 从中序遍历数组中找到根节点的下标
if let ind = inorder.firstIndex(of: rootValue) {
index = ind
}
// 递归
root.left = helper(preorder: preorder,
preorderBegin: preorderBegin + 1,
preorderEnd: preorderBegin + 1 + index - inorderBegin,
inorder: inorder,
inorderBegin: inorderBegin,
inorderEnd: index)
root.right = helper(preorder: preorder,
preorderBegin: preorderBegin + 1 + index - inorderBegin,
preorderEnd: preorderEnd,
inorder: inorder,
inorderBegin: index + 1,
inorderEnd: inorderEnd)
return root
}
}106 从中序与后序遍历序列构造二叉树
class Solution_0106 {
func buildTree(inorder: [Int], inorderBegin: Int, inorderEnd: Int, postorder: [Int], postorderBegin: Int, postorderEnd: Int) -> TreeNode? {
if postorderEnd - postorderBegin < 1 {
return nil
}
// 后序遍历数组的最后一个元素作为分割点
let rootValue = postorder[postorderEnd - 1]
let root = TreeNode(rootValue)
if postorderEnd - postorderBegin == 1 {
return root
}
// 从中序遍历数组中找到根节点的下标
var delimiterIndex = 0
if let index = inorder.firstIndex(of: rootValue) {
delimiterIndex = index
}
root.left = buildTree(inorder: inorder,
inorderBegin: inorderBegin,
inorderEnd: delimiterIndex,
postorder: postorder,
postorderBegin: postorderBegin,
postorderEnd: postorderBegin + (delimiterIndex - inorderBegin))
root.right = buildTree(inorder: inorder,
inorderBegin: delimiterIndex + 1,
inorderEnd: inorderEnd,
postorder: postorder,
postorderBegin: postorderBegin + (delimiterIndex - inorderBegin),
postorderEnd: postorderEnd - 1)
return root
}
}106 从中序与后序遍历序列构造二叉树
object Solution {
def buildTree(inorder: Array[Int], postorder: Array[Int]): TreeNode = {
// 1、如果长度为0，则直接返回null
var len = inorder.size
if (len == 0) return null
// 2、后序数组的最后一个元素是当前根元素
var rootValue = postorder(len - 1)
var root: TreeNode = new TreeNode(rootValue, null, null)
if (len == 1) return root // 如果数组只有一个节点，就直接返回
// 3、在中序数组中找到切割点的索引
var delimiterIndex: Int = inorder.indexOf(rootValue)
// 4、切分数组往下迭代
root.left = buildTree(inorder.slice(0, delimiterIndex), postorder.slice(0, delimiterIndex))
root.right = buildTree(inorder.slice(delimiterIndex + 1, len), postorder.slice(delimiterIndex, len - 1))
root // 返回root，return关键字可以省略
}
}105 从前序与中序遍历序列构造二叉树
object Solution {
def buildTree(preorder: Array[Int], inorder: Array[Int]): TreeNode = {
// 1、如果长度为0，直接返回空
var len = inorder.size
if (len == 0) return null
// 2、前序数组的第一个元素是当前子树根节点
var rootValue = preorder(0)
var root = new TreeNode(rootValue, null, null)
if (len == 1) return root // 如果数组元素只有一个，那么返回根节点
// 3、在中序数组中，找到切割点
var delimiterIndex = inorder.indexOf(rootValue)
// 4、切分数组往下迭代
root.left = buildTree(preorder.slice(1, delimiterIndex + 1), inorder.slice(0, delimiterIndex))
root.right = buildTree(preorder.slice(delimiterIndex + 1, preorder.size), inorder.slice(delimiterIndex + 1, len))
root
}
}106 从中序与后序遍历序列构造二叉树
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
pub fn build_tree(inorder: Vec<i32>, postorder: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
if inorder.is_empty() {
return None;
}
let mut postorder = postorder;
let root = postorder.pop().unwrap();
let index = inorder.iter().position(|&x| x == root).unwrap();
let mut root = TreeNode::new(root);
root.left = Self::build_tree(inorder[..index].to_vec(), postorder[..index].to_vec());
root.right = Self::build_tree(inorder[index + 1..].to_vec(), postorder[index..].to_vec());
Some(Rc::new(RefCell::new(root)))
}
}105 从前序与中序遍历序列构造二叉树
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
pub fn build_tree(preorder: Vec<i32>, inorder: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
if preorder.is_empty() {
return None;
}
let root = preorder[0];
let index = inorder.iter().position(|&x| x == root).unwrap();
let mut root = TreeNode::new(root);
root.left = Self::build_tree(preorder[1..index + 1].to_vec(), inorder[0..index].to_vec());
root.right = Self::build_tree(
preorder[index + 1..].to_vec(),
inorder[index + 1..].to_vec(),
);
Some(Rc::new(RefCell::new(root)))
}
}public TreeNode BuildTree(int[] inorder, int[] postorder)
{
if (inorder.Length == 0 || postorder.Length == null) return null;
int rootValue = postorder.Last();
TreeNode root = new TreeNode(rootValue);
int delimiterIndex = Array.IndexOf(inorder, rootValue);
root.left = BuildTree(inorder.Take(delimiterIndex).ToArray(), postorder.Take(delimiterIndex).ToArray());
root.right = BuildTree(inorder.Skip(delimiterIndex + 1).ToArray(), postorder.Skip(delimiterIndex).Take(inorder.Length - delimiterIndex - 1).ToArray());
return root;
}
