代码训练营Day.20 | 654. 最大二叉树， 617. 合并二叉树，700. 二叉搜索树中的搜索，98. 验证二叉搜索树

本文主要是介绍代码训练营Day.20 | 654. 最大二叉树， 617. 合并二叉树，700. 二叉搜索树中的搜索，98. 验证二叉搜索树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

654. 最大二叉树

1. LeetCode链接

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

2. 题目描述

3. 解法

与知道中序和后序数列的情况下啊构造树一样，将左右区间标出更省空间。

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

不太省的

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

617. 合并二叉树

1. LeetCode链接

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

2. 题目描述

3. 解法

递归，如代码所示。让root1最终承载最后的树。

class Solution {
public:TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {if (root1 == NULL) return root2;if (root2 == NULL) return root1;root1->val += root2->val;root1->left = mergeTrees(root1->left, root2->left);root1->right = mergeTrees(root1->right, root2->right);return root1;}
};

迭代法，与判断二叉树是否对称相似，两个两个走，注意，先判断是否两个都不是NULL而可以push，再考虑root1子树是NULL的情况而替换成root2子树。for循环注意stride。

class Solution {
public:TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {if (root1 == NULL) return root2;if (root2 == NULL) return root1;queue<TreeNode*> qu;qu.push(root1);qu.push(root2);while (!qu.empty()) {int size = qu.size();for (int i = 0; i < size; i+=2) {TreeNode* cur1 = qu.front();qu.pop();TreeNode* cur2 = qu.front();qu.pop();cur1->val += cur2->val;if (cur1->left != NULL && cur2->left != NULL) {qu.push(cur1->left);qu.push(cur2->left);}if (cur1->right != NULL && cur2->right != NULL) {qu.push(cur1->right);qu.push(cur2->right);}if (cur1->left == NULL) cur1->left = cur2->left;if (cur1->right == NULL) cur1->right = cur2->right;}}return root1;    }
};

700. 二叉搜索树中的搜索

1. LeetCode链接

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

2. 题目描述

3. 解法

1. 普通树

迭代，普普通通遍历。

class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {queue<TreeNode*> qu;qu.push(root);while (!qu.empty()) {int size = qu.size();for (int i = 0; i < size; i++) {TreeNode* cur = qu.front();qu.pop();if (cur->val == val) return cur;if (cur->left) qu.push(cur->left);if (cur->right) qu.push(cur->right);}}return NULL;}
};

递归，在判断root->val之前，一定要确保root != NULL。

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

2. 二叉搜索树

二叉搜索树是一个有序树：

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
• 它的左、右子树也分别为二叉搜索树

递归：

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

迭代：

class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {queue<TreeNode*> qu;qu.push(root);while (!qu.empty()) {int size = qu.size();for (int i = 0; i < size; i++) {TreeNode* cur = qu.front();qu.pop();if (cur->val == val) return cur;else if (cur->val > val && cur->left != NULL) qu.push(cur->left);else if (cur->val < val && cur->right != NULL) qu.push(cur->right);}}return NULL;}
};

98. 验证二叉搜索树

1. LeetCode链接

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

2. 题目描述

3. 解法

1）递归，一棵树是否为有效二叉搜索树，取决于两个条件：1. 两棵子树都是二叉搜索树；2. 左子树的最大值小于root->val，右子树的最小值大于root->val。

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

2）中序遍历后的数组是否单调递增！可以构造数组，也有不构造数组的方法。记录最大值或者上一个结点，及在中序递归时，如果是二叉搜索树，下一个要遍历的结点值必大于当前值。否则就不是二叉搜索树。

## 记录最大值。
class Solution {
public:long long maxVal = LONG_MIN; // 因为后台测试数据中有int最小值bool isValidBST(TreeNode* root) {if (root == NULL) return true;bool left = isValidBST(root->left);// 中序遍历，验证遍历的元素是不是从小到大if (maxVal < root->val) maxVal = root->val;else return false;bool right = isValidBST(root->right);return left && right;}
};

 

## 记录结点。
class Solution {
public:TreeNode* pre = NULL; // 用来记录前一个节点bool isValidBST(TreeNode* root) {if (root == NULL) return true;bool left = isValidBST(root->left);if (pre != NULL && pre->val >= root->val) return false;pre = root; // 记录前一个节点bool right = isValidBST(root->right);return left && right;}
};

这篇关于代码训练营Day.20 | 654. 最大二叉树， 617. 合并二叉树，700. 二叉搜索树中的搜索，98. 验证二叉搜索树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---