代码随想录算法训练营第23期day19| 654.最大二叉树、617.合并二叉树、700.二叉搜索树中的搜索、98.验证二叉搜索树

目录

一、（leetcode 654）最大二叉树

二、（leetcode 617）合并二叉树

三、（leetcode 700）二叉搜索树中的搜索

四、（leetcode 98）验证二叉搜索树

---

一、（leetcode 654）最大二叉树

力扣题目地址

状态：AC。

和昨天的中序+后/前序遍历序列构建二叉树思路类似，每次递归寻找数组中的最大值，根据最大值的索引来切分左右子序列进行递归生成，可以用索引下标来避免重复生成vector带来的开销

class Solution {
public:TreeNode* traversal(vector<int>& nums, int begin, int end){if(begin == end) { return nullptr; }int max_num = INT_MIN, max_index = begin;// 确定最大值的索引for(int i = begin; i < end; ++i){if(max_num < nums[i]){max_num = nums[i];max_index = i;}}TreeNode* node = new TreeNode(max_num);// 进行左右子数组划分int left_left = begin, left_right = max_index;int right_left = max_index + 1, right_right = end;node->left = traversal(nums, left_left, left_right);node->right = traversal(nums, right_left, right_right);return node;}TreeNode* constructMaximumBinaryTree(vector<int>& nums) {return traversal(nums, 0, nums.size());}
};

二、（leetcode 617）合并二叉树

力扣题目链接

状态：AC。

使用的方法可以AC但是不够简洁，留待后续改进

class Solution {
public:TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {//进行前序遍历，如果两棵树都为空则返回空节点if(root1 == nullptr && root2 == nullptr){return nullptr;}TreeNode* node = new TreeNode(0);if(root1 != nullptr && root2 != nullptr){node->val = root1->val + root2->val;node->left = mergeTrees(root1->left, root2->left);node->right = mergeTrees(root1->right, root2->right);}else if(root1){node->val = root1->val;node->left = mergeTrees(root1->left, nullptr);node->right = mergeTrees(root1->right, nullptr);}else{node->val = root2->val;node->left = mergeTrees(nullptr, root2->left);node->right = mergeTrees(nullptr, root2->right);}return node;  }
};

三、（leetcode 700）二叉搜索树中的搜索

力扣题目地址

状态：AC。

简单的前序遍历比较

class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {if(root == nullptr) return nullptr;//前序遍历if(root->val == val){return root;}else if(root->val < val){return searchBST(root->right, val);}else{return searchBST(root->left, val);}return nullptr;}
};

四、（leetcode 98）验证二叉搜索树

力扣题目链接

状态：思路错误，不能简单地比较根节点和左右子节点的大小。

这道题可以通过中序遍历的顺序判断值是不是递增来判断，注意除了上面的那个思路问题，在实现时用于比较的值maxVal需要使用long long来初始化，以防测试用例中有INT_MIN。

class Solution {
public:long long maxVal = LONG_MIN;bool isValidBST(TreeNode* root) {if(root == nullptr) return true;bool left = isValidBST(root->left);//中序遍历查看是否符合递增if(root->val > maxVal){maxVal = root->val;}else{return false;}bool right = isValidBST(root->right);return left && right;}
};