算法打卡 Day22（二叉树）-最大二叉树 + 合并二叉树 + 二叉搜索树中的搜索 + 验证二叉搜索树

Leetcode 654-最大二叉树

题目描述

https://leetcode.cn/problems/maximum-binary-tree/description/

解题思路

class Solution {
public:TreeNode* constructMaximumBinaryTree(vector<int>& nums) {TreeNode* root = new TreeNode(nums[0]);if (nums.size() == 1)return root;int maxIndex = 0;for (int i = 0; i < nums.size(); i++) {if (nums[i] > root->val) {root->val = nums[i];maxIndex = i;}}if (maxIndex > 0) {vector<int> left(nums.begin(), nums.begin() + maxIndex);root->left = constructMaximumBinaryTree(left);}if (maxIndex < nums.size() - 1) {vector<int> right(nums.begin() + maxIndex + 1, nums.end());root->right = constructMaximumBinaryTree(right);}return root;}
};

Leetcode 617-合并二叉树

题目描述

https://leetcode.cn/problems/merge-two-binary-trees/description/

解题思路

class Solution {
public:TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {if (root1 == nullptr)return root2;if (root2 == nullptr) return root1;TreeNode* root = new TreeNode(0);//定义一个新的节点接收结果root->val = root1->val + root2->val;root->left = mergeTrees(root1->left, root2->left);root->right = mergeTrees(root1->right, root2->right);return root;}
};

Leetcode 700-二叉搜索树中的搜索

题目描述

https://leetcode.cn/problems/search-in-a-binary-search-tree/description/

解题思路

二叉搜索树：二叉搜索树自带顺序，根节点的左子树的节点要比根节点的值都小，右子树的节点的值比根节点的都大。

递归法：

class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {if (root == nullptr || root->val == val) return root;TreeNode* result = nullptr;if (root->val > val) result = searchBST(root->left, val);else if (root->val < val) result = searchBST(root->right, val);return result;}
};

迭代法：

class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {while (root!=nullptr){if (root->val > val) root = root->left;else if (root->val < val) root = root->right;else return root;}return nullptr;}
};

Leetcode 98-验证二叉搜索树

题目描述

https://leetcode.cn/problems/validate-binary-search-tree/description/

解题思路

要充分利用二叉搜索树的特性，要使用中序遍历（左中右），在这样的遍历顺序下，遍历的值是逐渐递增的。

要注意二叉搜索树不仅仅是中节点的值大于左节点小于右节点，同时需要保证中节点的值大于左子树的所有值，小于右子树的所有值。

class Solution {
public:TreeNode* pre = nullptr;bool isValidBST(TreeNode* root) {if (root == nullptr)return true;bool left = isValidBST(root->left);if (pre != nullptr && root->val <= pre->val)return false;else pre = root;bool right = isValidBST(root->right);return left && right;}
};