654.最大二叉树
思路
建树顺序：
本质上与中序+前、后序建树方法一致，关键在于熟练掌握建树流程。
题解
class Solution {
public:
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
if(nums.size() == 0)return nullptr;
int max = INT_MIN,index = 0;
for(int i = 0;i<nums.size();i++)
{
if(nums[i]>max)
{
max = nums[i];
index = i;
}
}
TreeNode *root = new TreeNode(max);
vector<int> left(nums.begin(),nums.begin()+index);
vector<int> right(nums.begin()+index+1,nums.end());
root->left = constructMaximumBinaryTree(left);
root->right = constructMaximumBinaryTree(right);
return root;
}
};
617.合并二叉树
思路
合并二叉树过程：
很好想的前序遍历：先处理当前节点，看看怎么合并，然后再遍历左或者右（顺序没要求），注意优化后代码的思路！
复杂点在于条件的判断：
- 同时遍历两树
- 都有节点相加
- 一个没有一个有，把没有的视为空，继续遍历有的->直到没有
题解
class Solution {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
// if(root1==nullptr && root2==nullptr)return nullptr;
// TreeNode *node = nullptr;
// if(root1==nullptr&&root2!=nullptr || root1!=nullptr&&root2==nullptr)
// {
// if(root1!=nullptr)
// {
// node = new TreeNode(root1->val);
// node->left = mergeTrees(root1->left,nullptr);
// node->right = mergeTrees(root1->right,nullptr);
// }
// if(root2!=nullptr)
// {
// node = new TreeNode(root2->val);
// node->left = mergeTrees(nullptr,root2->left);
// node->right = mergeTrees(nullptr,root2->right);
// }
// }
// if(root1!=nullptr&&root2!=nullptr)
// {
// node = new TreeNode(root1->val+root2->val);
// node->left = mergeTrees(root1->left,root2->left);
// node->right = mergeTrees(root1->right,root2->right);
// }
// return node;
//将都为空与其中一个为空的情况合二为一
//优化方法利用已有的树，不需要额外建立空间
if(root1 == nullptr)return root2;
else if(root2 == nullptr)return root1;
//都不为空
root1->val += root2->val;
root1->left = mergeTrees(root1->left, root2->left);
root1->right = mergeTrees(root1->right, root2->right);
return root1;
}
};
700.二叉搜索树中的搜索
题目链接：700.二叉搜索树中的搜索
文档讲解：代码随想录
状态：轻松AC
思路
本题开始介绍使用二叉搜索树，其定义为：
- 节点的左子树只包含 严格小于 当前节点的数。
- 节点的右子树只包含 严格大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
充要条件：树的中序遍历是严格单调递增
重要性质：二叉搜索树的前序遍历类似于二分查找
对于在二叉搜索树中的应用，因为是有序树，在递归时没有了回溯的隐藏步骤；在迭代法时也不用复杂的队列操作，仅根据大小顺序一直往底部搜索
题解
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
// 递归法,无回溯过程qw
// TreeNode *res = nullptr;
// //if else 中间不能有其他语句
// if(root == nullptr || root->val == val)return root;
// else if(root->val>val)
// {
// res = searchBST(root->left, val);
// }
// else if(root->val<val)
// {
// res = searchBST(root->right, val);
// }
// return res;
//迭代法
while(root != nullptr)
{
if(root->val > val)root = root->left;
else if(root->val < val)root = root->right;
else return root;
}
return root;
}
};
98.验证二叉搜索树
题目链接：98.验证二叉搜索树
文档讲解：代码随想录
状态：了解性质后轻松AC，但是待优化地方很多
思路
本来没思路，悄悄看一眼题解，发现了上题所说的关键性质：树的中序遍历是严格单调递增，
那么我建立一个全局的vector数组，每次加入元素时就和最后元素比较大小，当然没问题。（存在的问题：当vector为空时不能进行比较操作，里面必须有数）
既然每次加入元素仅和最后元素比较大小，那可以使用一个全局变量保存上一次，避免维护数组。（存在的问题：题解使用了INT_MIN，需要面向结果变成使用long long数据类型）
每次还要根据题解给出的数据操作？不行，使用定义的TreeNode*节点保存上一个状态，和上一个区别在于有一个nullptr作为初始值。
本题加强理解树的三种递归遍历方法，左右仅仅都是方向的优先性，关键处理都在于中的位置！
题解
class Solution {
public:
//vector<int> vec;
//long long pre = LLONG_MIN;
TreeNode* pre;
bool isValidBST(TreeNode* root) {
if(root == nullptr)return true;
bool left = isValidBST(root->left);
// if(vec.empty())vec.push_back(root->val);
// else if(root->val<=vec[vec.size()-1])
// {
// return false;
// }
// else
// {
// vec.push_back(root->val);
// }
if(pre!=nullptr && root->val<=pre->val)return false;
pre = root;
bool right = isValidBST(root->right);
return left&&right;
}
};