- 106. 从中序与后序遍历序列构造二叉树
- 105.从前序与中序遍历序列构造二叉树
- 654.最大二叉树
https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
/**
* 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* transfer(vector<int> &inorder,vector<int> &postorder){
// 分割出空节点，返回
if(postorder.size()==0) return nullptr;
// 取出后序的最后一个作为分割点
int rootValue = postorder[postorder.size() - 1];
TreeNode *root = new TreeNode(rootValue);
// 分割到只剩叶子结点，给叶子结点赋值
if(postorder.size() == 1) return root;
int i = 0;
for(; i < inorder.size(); i++){
if(inorder[i] == rootValue) break;
}
// 按照分割点切分中序数组
vector<int> leftInorder (inorder.begin(), inorder.begin() + i); // [0,i]
vector<int> rightInorder (inorder.begin() + i + 1, inorder.end()); // [i+1,end]
// 按照中序左右数组的大小切分后序数组
postorder.resize(postorder.size() - 1);
vector<int> leftPostorder (postorder.begin(), postorder.begin() + leftInorder.size());
vector<int> rightPostorder (postorder.begin() + leftInorder.size(), postorder.end());
// 重构树
root->left = transfer(leftInorder,leftPostorder);
root->right = transfer(rightInorder,rightPostorder);
return root;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if(inorder.size()==0 || postorder.size()==0) return nullptr;
return transfer(inorder,postorder);
}
};
优化：将递归中创建的中序后序的左右序列数组，替换成用下标定位，节约空间。
/**
* 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:
// 这里的inE postE 都是闭区间，相当于size
TreeNode* transfer(vector<int> &inorder,int inS,int inE,vector<int> &postorder,int postS,int postE){
// 当前为空节点 返回
if(postE == postS) return nullptr;
// 获取分割点
int rootValue = postorder[postE - 1];
TreeNode *root = new TreeNode(rootValue);
if(postE - postS == 1) return root; //叶子结点直接返回
// 用分割点划分中序数组
int i = inS;
for(;i < inE; i++){
if(inorder[i] == rootValue) break;
}//分别设置左右数组的下标
int leftInS = inS;
int leftInE = i;
int rightInS = i + 1;
int rightInE = inE;
// 用中序数组的左右序列大小划分后序数组
int leftPostS = postS;
int leftPostE = postS + i - inS;
int rightPostS = postS + i - inS;
int rightPostE = postE - 1; // 最后一位舍掉
// 构建树
root->left = transfer(inorder,leftInS,leftInE,postorder,leftPostS,leftPostE);
root->right = transfer(inorder,rightInS,rightInE,postorder,rightPostS,rightPostE);
return root;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if(inorder.size()==0 || postorder.size()==0) return nullptr;
return transfer(inorder,0,inorder.size(),postorder,0,postorder.size());
}
};
大致思路类似，把中序和后序的理解清楚然后中序前序就简单多了，只需要将前序序列起始结束的更新变一下即可。
/**
* 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* construct(vector<int> &preorder, int preS, int preE, vector<int>& inorder, int inS, int inE){
// 此时到达空节点，返回空叶子结点
if(preE == preS) return nullptr;
int rootValue = preorder[preS];
TreeNode *root = new TreeNode(rootValue);
// 此时序列中只有一个值，说明是叶子结点，直接返回
if(preE - preS == 1) return root;
// 根据前序的第一个节点找中序的分割点
int i;
for(i = inS; i < inE; i++){
if(inorder[i] == rootValue) break;
}
// 分割中序序列为左右两部分
int leftInS = inS;
int leftInE = i;
int rightInS = i + 1; //跳过根节点
int rightInE = inE;
// 根据中序的左右序列分割先序为左右两部分
preS = preS + 1;
int leftPreS = preS; // 根被取出来了，跳过根节点
int leftPreE = preS + i - inS;
int rightPreS = preS + i - inS;
int rightPreE = preE;
// 打印日志
// cout<<"--------"<
// for(int i = leftInS;i
// for(int i = rightInS;i
// for(int i = leftPreS;i
// for(int i = rightPreS;i
// 连接左右子树
root -> left = construct(preorder,leftPreS,leftPreE,inorder,leftInS,leftInE);
root -> right = construct(preorder,rightPreS,rightPreE,inorder,rightInS,rightInE);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if(preorder.size() == 0 || inorder.size() == 0) return nullptr;
return construct(preorder,0,preorder.size(),inorder,0,inorder.size());
}
};
https://leetcode-cn.com/problems/maximum-binary-tree/
大致思路和构建二叉树一样，但是过程更简单了，就是找左右子树的起始结束位置，然后对其连接再返回根节点。
/**
* 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* construct(vector<int>& num,int s,int e){
//到末尾了返回空叶子结点
if(e == s) return nullptr;
//找最大值,分割点
int maxNum = num[s],maxNumIndex=s;
for(int i = s+1; i < e; i++){
if(num[i]>maxNum) {
maxNum = num[i];
maxNumIndex=i;
}
}
TreeNode *root = new TreeNode(maxNum);
//只有一个元素返回叶子结点
if(e - 1 == s) return root;
//左子树下标
int leftS = s;
int leftE = maxNumIndex;
//右子树下标
int rightS = maxNumIndex + 1;
int rightE = e;
//连接左右子树
root -> left = construct(num,leftS,leftE);
root -> right = construct(num,rightS,rightE);
return root;
}
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
if(nums.size() == 0) return nullptr;
return construct(nums,0,nums.size());
}
};
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）