目录
构造二叉树类题目思路：一般采用前序遍历，先构造根节点再构造左右节点，步骤如下：1.寻找分割点来构造头节点 2.切割左右数组，递归构造左右子树 3.确定递归函数返回值和终止条件，一般要返回树节点，而终止条件一般为区间切割到只剩下一个元素
一些可能用的上的知识点：
1.前序遍历和中序遍历结果数组可以唯一确定一棵树，因为是同一棵树，所有左右子树构成的子数组大小相同，节点数值一一对应。前序遍历的数组，头节点在前，中序遍历结果数组，头节点两边是左右子树的遍历结果。
2.同理后序遍历和中序遍历可以唯一确定一棵树，且后序遍历结果数组头节点在后。
3.二叉搜索树中序遍历结果是一个有序数组。
4.c++ vector用另一个vector初始化时，vector<int> a(nums.begin()+1, nums.end()-2);中a包含nums.begin()+1，不包含nums.end()-2，也就是包含的区间是左闭右开区间
5.vec.front()返回vector的第一个元素；vec.erase(*it)删去迭代器指向的元素，vec数组大小-1；
106.从中序与后序遍历序列构造二叉树
根据一棵树的中序遍历与后序遍历构造二叉树。
注意: 你可以假设树中没有重复的元素。
例如，给出
- 中序遍历 inorder = [9,3,15,20,7]
- 后序遍历 postorder = [9,15,7,20,3] 返回如下的二叉树：
思路：
1.寻找分割点：后序遍历结果数组末尾元素就是根节点
2.切割左右数组：在中序数组里找根节点值所在位置下标index，这里可以用unordered_map来存放中序结果以提高查找效率；中序之左为左子树，中序之右为右子树数组；再根据中序左右数组长度确定后续左右数组，用以递归遍历
3.递归函数返回值：返回树节点；函数参数：前序数组，后序数组；
/**
* 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>& inorder,vector<int>& postorder){
if(postorder.size()==0)return NULL;
//用后序遍历末尾元素构造中节点
int nodevalue=postorder[postorder.size()-1];
// cout<<"nodevalue="<<nodevalue<<endl;
TreeNode* node =new TreeNode(nodevalue);
//终止条件：区间切割到只剩一个元素；
if(postorder.size()==1)return node;
//寻找中序分割点
int index;
for(index=0;index<inorder.size();index++){
if(inorder[index]==nodevalue)break;
}
// cout<<"index="<<index<<endl;
//切割中序数组
vector<int>newinoderleft(inorder.begin(),inorder.begin()+index);
vector<int>newinoderright(inorder.begin()+index+1,inorder.end());
//切割后序数组,先舍弃构造过的元素
postorder.resize(postorder.size()-1);
// cout<<"poatindex after slide:"<<postorder.size()<<endl;
vector<int>newpostleft(postorder.begin(), postorder.begin()+newinoderleft.size());
vector<int>newpostright(postorder.begin()+newinoderleft.size(),postorder.end());
//递归构造左右子树
node->left=construct(newinoderleft,newpostleft);
node->right=construct(newinoderright,newpostright);
return node;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if(inorder.size()==0||postorder.size()==0)return NULL;
return construct(inorder, postorder);
}
};105.从前序与中序遍历序列构造二叉树
根据一棵树的前序遍历与中序遍历构造二叉树。
注意: 你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树：
思路：用前序数组第一个元素去切割中序数组，其余与上一题相同
/**
* 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* constuct(vector<int>& preorder, vector<int>& inorder){
if(preorder.size()==0)return nullptr;
//构造中节点
int nodevalue=preorder.front();
TreeNode* node =new TreeNode(nodevalue);
// cout<<"nodevalue:"<<nodevalue<<endl;
if(preorder.size()==1)return node;//
//寻找切割点
int index;
for(index=0; index<inorder.size(); index++){
if(inorder[index]==nodevalue)break;
}
// cout<<"index of inorder slide:"<<index<<endl;
//切割中序数组,注意用vector初始化另一个vector是左闭右开的
vector<int>newinoderleft(inorder.begin(),inorder.begin()+index);
vector<int>newinorderright(inorder.begin()+index+1, inorder.end());
//切割前序数组,先舍弃用过的
// cout<<"preorder before slide:"<<preorder.size()<<endl;
preorder.erase(preorder.begin());
// cout<<"preorder after slide:"<<preorder.size()<<endl;
// cout<<"preorder[0]"<<preorder[0]<<endl;
vector<int>newpreleft(preorder.begin(),preorder.begin()+newinoderleft.size());
vector<int>newpreright(preorder.begin()+newinoderleft.size(),preorder.end());
//递归构造左右子树
node->left=constuct(newpreleft,newinoderleft);
node->right=constuct(newpreright,newinorderright);
return node;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if(preorder.size()==0||inorder.size()==0)return nullptr;
return constuct(preorder,inorder);
}
};654.最大二叉树
给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：
- 二叉树的根是数组中的最大元素。
- 左子树是通过数组中最大值左边部分构造出的最大二叉树。
- 右子树是通过数组中最大值右边部分构造出的最大二叉树。
通过给定的数组构建最大二叉树，并且输出这个树的根节点。
示例 ：
提示：
给定的数组的大小在 [1, 1000] 之间。
思路：找到分割点，划分左右数组，构造节点，递归构造左右子树
/**
* 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* constructMaximumBinaryTree(vector<int>& nums) {
//递归终止条件：数组切割到只剩一个元素，此时节点就是叶子节点了
//构造节点然后返回即可
if(nums.size()==1){
TreeNode* node= new TreeNode(nums[0]);
return node;
}
//寻找区间分割点
int maxIndex=0;
int maxvalue=0;
for(int i=0;i<nums.size();i++){
if(nums[i]>maxvalue) {
maxvalue=nums[i];
maxIndex=i;
}
}
//中
TreeNode* node= new TreeNode(maxvalue);
//左,判断一下左边是否还有元素，如果Index=0，左边就没有元素了
if(maxIndex>0){
vector<int>newvec(nums.begin(),nums.begin()+maxIndex);
node->left=constructMaximumBinaryTree(newvec);
}
//右，同样要判断一下右边是否还有元素
if(maxIndex<(nums.size()-1)){
vector<int>newvec(nums.begin()+maxIndex+1,nums.end());
node->right=constructMaximumBinaryTree(newvec);
}
return node;
}
};
