前言
记录 三十八的四、二叉树构建通过层序遍历的数组实现。
层序遍历中,某个节点下标是i,那么左孩子的下标2i+1,右孩子的下标2i+2。这是统一的规律。
那么通过中序序列和后序序列如何构造二叉树?通过中序序列和前序序列如何构造二叉树?通过前序序列和后序序列如何构造二叉树?
一、【106.从中序与后序遍历序列构造二叉树】题目阅读
给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。
示例 1:
输入:inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出:[3,9,20,null,null,15,7]
示例 2:
输入:inorder = [-1], postorder = [-1]
输出:[-1]
提示:
1 <= inorder.length <= 3000
postorder.length == inorder.length
-3000 <= inorder[i], postorder[i] <= 3000
inorder 和 postorder 都由 不同 的值组成
postorder 中每一个值都在 inorder 中
inorder 保证是树的中序遍历
postorder 保证是树的后序遍历
二、【106.从中序与后序遍历序列构造二叉树】思路获取
拿到题目分析:尝试看某个元素左右相邻的数值规律,没有成型的思路,所以先通过参考学习思路。
- 中序:左中右;后序:左右中。
- 确定后序的最后一位一定是中间节点(整个树的根节点)。
- 拿到中间节点,在中序中找中间节点的位置,该位置左边区间所有数值是它的左子树;该位置右边区间所有数值是它的右子树。以中间节点为界,分成左右两边区间。
- 以左区间内容在后序中比较,确定后序数组中左右的分界;相应剩下的是右区间。
- 深入左区间,重复2-4步骤,可以建立左子树;深入右区间,重复2-4步骤,可以建立右子树。
- 核心:
- 后序数组确定中间节点;
- 中序数组以中间节点为界,划分左右区间;
- 以分出来的左右区间,确定后序左右子树的界限。再次重复。(这个重复就是递归逻辑)
–
三、【106.从中序与后序遍历序列构造二叉树】代码实现
有了思路后,先尝试代码实现:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
//终止条件
if(postorder.size() == 0) return nullptr;
//终止条件,如果后序只有一个节点,是一个节点的树。
TreeNode* root = new TreeNode(postorder[postorder.size()-1]);//创建根节点
if(postorder.size() == 1) return root;//返回上一层,把这个创建的根节点返回去
//在中序数组中分出左右两边子树,整个区间坚持左闭右闭。
int index = 0;
for(;index < inorder.size();index++){
if(inorder[index] == postorder[postorder.size()-1]) break;
}
//左子树长度是index
vector<int> lefttree_inorder;
for(int i = 0;i < index;i++){
lefttree_inorder.push_back(inorder[i]);
}
//右子树长度inorder.size()-index-1
vector<int> righttree_inorder;
for(int i = index+1,j = 0;i < inorder.size();i++){
righttree_inorder.push_back(inorder[i]);
}
//从后序数组中找到左右区间的分界
vector<int> lefttree_postorder;
for(int i = 0;i < index;i++){//截取长度index
lefttree_postorder.push_back(postorder[i]);
}
vector<int> righttree_postorder;
for(int i = index;i < postorder.size()-1;i++){//从下标index开始,到最后一个元素之前
righttree_postorder.push_back(postorder[i]);
}
//深入左子树和右子树
TreeNode* leftroot = buildTree(lefttree_inorder,lefttree_postorder);
TreeNode* rightroot = buildTree(righttree_inorder,righttree_postorder);
root->left = leftroot;
root->right = rightroot;
return root;
}
};
对比参考代码:
-
在中序数组分左右时:
// 左闭右开区间:[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());
-
参考使用构造函数,遵循左闭右开区间规则;代码实现使用for循环填充元素,遵循左闭右闭区间规则。
改进【使用下标分割】
【使用下标分割】思路:
- 上面每一次递归,分割数组都是建立4个新数组,开辟空间后,传递给下一层;
- 使用同一个数组,每一层传入下标值,这样不用新建数组。
- 不过8个下标要确认好。
【使用下标分割】代码实现
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* build(vector<int>& inorder,vector<int>& postorder,int inorder_left,int inorder_right,int postorder_left,int postorder_right){
//左闭右开规则
//终止条件,对应后序数组为空
if(postorder_left == postorder_right) return nullptr;
//终止条件,后序只有一个节点,是一个节点的树。
TreeNode* root = new TreeNode(postorder[postorder_right-1]);
if(postorder_right - postorder_left == 1) return root;
//找中间节点在中序数组的位置
int index = inorder_left;
for(;index < inorder_right;index++){
if(inorder[index] == postorder[postorder_right-1]) break;
}
//中序数组左区间:[inorder_left,index)。右区间:[index+1,inorder_right)
int leftinorderbegin = inorder_left;
int leftinorderend = index;
int rightinorderbegin = index+1;
int rightinorderend = inorder_right;
//长度:index-inorder_left
//找后序数组的左右分界:[postorder_left,postorder_left+index-inorder_left)。右区间传参:[postorder_left+index-inorder_left,postorder_right-1)
int leftpostbegin = postorder_left;
int leftpostend = postorder_left+index-inorder_left;
int rightpostbegin = postorder_left+index-inorder_left;
int rightpostend = postorder_right-1;
root->left = build(inorder,postorder,leftinorderbegin,leftinorderend,leftpostbegin,leftpostend);
root->right = build(inorder,postorder,rightinorderbegin,rightinorderend,rightpostbegin,rightpostend);
return root;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
return build(inorder,postorder,0,inorder.size(),0,postorder.size());
}
};
四、【105.从前序与中序遍历序列构造二叉树】题目阅读
给定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的先序遍历, inorder 是同一棵树的中序遍历,请构造二叉树并返回其根节点。
示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
示例 2:
输入: preorder = [-1], inorder = [-1]
输出: [-1]
提示:
1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder 和 inorder 均 无重复 元素
inorder 均出现在 preorder
preorder 保证 为二叉树的前序遍历序列
inorder 保证 为二叉树的中序遍历序列
五、【105.从前序与中序遍历序列构造二叉树】思路和代码实现
思路
和【106.通过中序和后序构建二叉树】基本一致,区别:前序的中在最前面。
代码实现1【创建数组】
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
//这个子树没有元素。说明空
if(preorder.size() == 0) return nullptr;
//子树只有一个元素
TreeNode* root = new TreeNode( preorder[0]);
if(preorder.size() == 1) return root;
//子树有多个元素
//拿着root的值去分割inorder
int index = 0; //index就是长度
for(;index < inorder.size();index++){
if(inorder[index] == preorder[0]) break;
}
//左闭右开
vector<int> leftinorder(inorder.begin(),inorder.begin()+index);
vector<int> rightinorder(inorder.begin()+index+1,inorder.end());
//用左右区间分割前序数组
vector<int> leftpreorder(preorder.begin()+1,preorder.begin()+1+index);
vector<int> rightpreorder(preorder.begin()+1+index,preorder.end());
root->left = buildTree(leftpreorder,leftinorder);
root->right = buildTree(rightpreorder,rightinorder);
return root;
}
};
代码实现2【下标分割,不创建数组】
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* build(vector<int>& preorder,vector<int>& inorder,int preorder_left,int preorder_right,int inorder_left,int inorder_right){
//这个子树没有元素。说明空
if(preorder_left == preorder_right) return nullptr;
//子树只有一个元素
TreeNode* root = new TreeNode(preorder[preorder_left]);
if(preorder_right - preorder_left == 1) return root;
//子树有多个元素
//拿着root的值去分割inorder
int index = inorder_left;
for(;index < inorder_right;index++){
if(inorder[index] == preorder[preorder_left]) break;
}
//左闭右开
int leftinorderbegin = inorder_left;
int leftinorderend = index;
int rightinorderbegin = index+1;
int rightinorderend = inorder_right;
//用左右区间分割前序数组
int leftpreorderbegin = preorder_left+1;
int leftpreorderend = preorder_left+1+index-inorder_left;
int rightpreorderbegin = leftpreorderend;
int rightpreorderend = preorder_right;
root->left = build(preorder,inorder,leftpreorderbegin,leftpreorderend,leftinorderbegin,leftinorderend);
root->right = build(preorder,inorder,rightpreorderbegin,rightpreorderend,rightinorderbegin,rightinorderend);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return build(preorder,inorder,0,preorder.size(),0,inorder.size());
}
};
总结
构造二叉树:
(欢迎指正,转载标明出处)
标签:遍历,TreeNode,int,right,二叉树,序列,left,inorder,postorder From: https://blog.csdn.net/danaaaa/article/details/140495310