题目：最大二叉树
思路：和昨天的最后两题即为相似，重要的是单层逻辑和终止条件
终止条件：输入的数组大小为0或者为1（具体代码中有写）
单层循环逻辑：找到数组中的最大值，将最大值作为创建节点的值，之后通过遍历逻辑创建左右节点（比昨天的题目简单）
返回值：节点
class Solution {
public:
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
if(nums.size() == 0) //这个终止条件是碰到区间左右切割后单个区间为空的情况
{
return nullptr;
}
auto max_num = max_element(nums.begin(),nums.end());
TreeNode* node = new TreeNode(*max_num);
if(nums.size() == 1) //这个终止条件是碰到区间左右切割后单个区间为1的情况
{
return node;
}
vector<int>left_num(nums.begin(),max_num);
vector<int>right_num(max_num+1,nums.end());
node->left = constructMaximumBinaryTree(left_num);
node->right = constructMaximumBinaryTree(right_num);
return node;
}
};题目：合并二叉树（居然没刷出来，太抽象了）
思路：本题目的核心是终止条件后跟的返回值，本体的终止条件有3个，左子树有值右子树没值，左子树没值右子树有值，以及左右子树都没有值。
情况一则返回root2即可，情况二返回root1，情况3已经包含在情况二和情况一中
class Solution {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if(root1 == nullptr)
{
return root2;
}
if(root2 == nullptr)
{
return root1;
}
TreeNode* node = new TreeNode(root1->val + root2->val);
node->left = mergeTrees(root1->left,root2->left);
node->right = mergeTrees(root1->right,root2->right);
return node;
}
};题目：二叉搜索树中的搜索
思路：
返回值：树节点
终止条件：如果找到了val或者是递归后的root为空
单层循环逻辑：通过递归的方式从左右子树那边获取树节点，若节点为空说明该子树中没有目标值，若节点不为空说明找到了节点并且返回值也为该节点，因此只需要将该值返回即可。
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
if(root == nullptr)
{
return nullptr;
}
if(root->val == val)
{
return root;
}
TreeNode* node_left = searchBST(root->left,val);
if(node_left != nullptr)
{
return node_left;
}
TreeNode* node_right = searchBST(root->right,val);
if(node_right != nullptr)
{
return node_right;
}
return node_right;
}
};题目：验证二叉搜索树（二刷没AC的题目）
思路：使用中序的方式，中序采用左中右的遍历方式符合验证二叉搜索树的排序方式，只要中序遍历的过程中前一个节点的值小于当前节点的值就符合搜索二叉树。
class Solution {
public:
TreeNode* pre = nullptr;
bool isValidBST(TreeNode* root) {
if(root == nullptr)
{
return true;
}
bool left = isValidBST(root->left); //左
if((pre != nullptr)&& (pre->val >= root->val)) //中
{
return false;
}
pre = root; //对比完成后将指针前移
bool right = isValidBST(root->right); //右
return left && right;
}
};
评论