参考：东哥带你刷二叉树（构造篇） | labuladong 的算法笔记
建议先过一遍：今天是二叉树~-CSDN博客，very重要！
然后再过一遍（理解怎么应用方法）：保研机试之[三道二叉树习题，思路为主]-CSDN博客
二叉树的构造问题一般都是使用「分解问题」的思路：构造整棵树 = 根节点 + 构造左子树 + 构造右子树。
第一题： 654. 最大二叉树 - 力扣（LeetCode）
动规写法直接秒了~
前序位置先找数组中最大值，创建新节点；后序位置填充新节点的左右指针
/**
* 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>& nums,int l,int r,int len){
if(l>r || l>=len || r<0){
return nullptr;
}
//前
/*寻找最大值*/
int find_max=0;
int idx=l;
for(int i=l;i<=r;i++){
if(find_max<nums[i]){
find_max=nums[i];
idx=i;
}
}
TreeNode* root=new TreeNode;
root->val=find_max;
TreeNode* left=construct(nums,l,idx-1,len);
//中
TreeNode* right=construct(nums,idx+1,r,len);
//后
root->left=left;
root->right=right;
return root;
}
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
int len=nums.size();
TreeNode* res=construct(nums,0,len-1,len);
return res;
}
};第二题： 105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）
这道题我原来做过：力扣--从前序与中序遍历序列构造二叉树-CSDN博客
如今一看，可能当时做的毫无章法，现在再来看这道题
一样的思路：前序位置先找数组中最大值，创建新节点；后序位置填充新节点的左右指针，只不过传递数组索引较为麻烦，我将preorder和inorder的左右索引都进行传递
/**
* 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 p_l,int p_r,int i_l,int i_r,int len){
if(p_l>p_r || i_l>i_r || p_l>=len || p_r<0 || i_l>=len || i_r<0){
return nullptr;
}
int cnt=preorder[p_l];
TreeNode* node=new TreeNode;
node->val=cnt;
int idx=0;
for(int i=i_l;i<=i_r;i++){
if(inorder[i]==cnt){
idx=i;
break;
}
}
int cnt_l=idx-i_l;
int cnt_r=i_r-idx;
//前
TreeNode* left=build(preorder,inorder,p_l+1,p_l+cnt_l,i_l,i_l+cnt_l-1,len);
//中
TreeNode* right=build(preorder,inorder,p_l+cnt_l+1,p_r,i_l+cnt_l+1,i_r,len);
//后
node->left=left;
node->right=right;
return node;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int len=preorder.size();
TreeNode* root=build(preorder,inorder,0,len-1,0,len-1,len);
return root;
}
};
