本文主要是介绍【LC刷题】DAY15:654 617 700 98,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
【LC刷题】DAY15:654 617 700 98
文章目录
- 【LC刷题】DAY15:654 617 700 98
- 654. 最大二叉树 [link](https://leetcode.cn/problems/maximum-binary-tree/description/)
- 617. 合并二叉树 [link](https://leetcode.cn/problems/merge-two-binary-trees/description/)
- 700. 二叉搜索树中的搜索 [link](https://leetcode.cn/problems/search-in-a-binary-search-tree/description/)
- 98. 验证二叉搜索树 [link](https://leetcode.cn/problems/validate-binary-search-tree/description/)
654. 最大二叉树 link
/*** 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) {return construct(nums, 0, nums.size() - 1);}TreeNode* construct(const vector<int>& nums, int left, int right){if(left > right){return nullptr;}int best = left;for(int i = left + 1; i<= right; ++ i){if(nums[i] > nums[best]){best = i;}}TreeNode* node = new TreeNode(nums[best]);node->left = construct(nums, left, best -1);node->right = construct(nums, best + 1, right);return node;}};
617. 合并二叉树 link
/*** 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* mergeTrees(TreeNode* t1, TreeNode* t2) {if(t1 == nullptr){return t2;}if(t2 == nullptr){return t1;}auto merge = new TreeNode(t1->val+ t2->val);merge->left = mergeTrees(t1->left, t2->left);merge->right = mergeTrees(t1->right, t2->right);return merge;}
};
700. 二叉搜索树中的搜索 link
/*** 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* searchBST(TreeNode* root, int val) {if(!root){return nullptr;}queue<TreeNode*> q;q.push(root);while(!q.empty()){auto node = q.front();q.pop();if(node->val == val){return node;}if(node->left) q.push(node->left);if(node->right) q.push(node->right);}return nullptr;}
};
98. 验证二叉搜索树 link
/*** 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:vector<int> vec;void traversal(TreeNode* root){if(root == nullptr) return;traversal(root->left);vec.push_back(root->val);traversal(root->right);}bool isValidBST(TreeNode* root) {vec.clear();traversal(root);for(int i = 1; i < vec.size(); i ++){if(vec[i] <= vec[i - 1]) return false;}return true;}
};
这篇关于【LC刷题】DAY15:654 617 700 98的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!