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

Leetcode 654-最大二叉树

题目形貌

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

解题思路

1. class Solution {
2. public:
3.     TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
4.         TreeNode* root = new TreeNode(nums[0]);
5.         if (nums.size() == 1)return root;
6.         int maxIndex = 0;
7.         for (int i = 0; i < nums.size(); i++) {
8.             if (nums[i] > root->val) {
9.                 root->val = nums[i];
10.                 maxIndex = i;
11.             }
12.         }
13.         if (maxIndex > 0) {
14.             vector<int> left(nums.begin(), nums.begin() + maxIndex);
15.             root->left = constructMaximumBinaryTree(left);
16.         }
17.         if (maxIndex < nums.size() - 1) {
18.             vector<int> right(nums.begin() + maxIndex + 1, nums.end());
19.             root->right = constructMaximumBinaryTree(right);
20.         }
21.         return root;
22.     }
23. };

复制代码

Leetcode 617-合并二叉树

题目形貌

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

解题思路

1. class Solution {
2. public:
3.     TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
4.         if (root1 == nullptr)return root2;
5.         if (root2 == nullptr) return root1;
6.         TreeNode* root = new TreeNode(0);//定义一个新的节点接收结果
7.         root->val = root1->val + root2->val;
8.         root->left = mergeTrees(root1->left, root2->left);
9.         root->right = mergeTrees(root1->right, root2->right);
10.         return root;
11.     }
12. };

复制代码

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

题目形貌

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

解题思路

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

1. class Solution {
2. public:
3.     TreeNode* searchBST(TreeNode* root, int val) {
4.         if (root == nullptr || root->val == val) return root;
5.         TreeNode* result = nullptr;
6.         if (root->val > val) result = searchBST(root->left, val);
7.         else if (root->val < val) result = searchBST(root->right, val);
8.         return result;
9.     }
10. };

复制代码

迭代法：

1. class Solution {
2. public:
3.     TreeNode* searchBST(TreeNode* root, int val) {
4.         while (root!=nullptr)
5.         {
6.             if (root->val > val) root = root->left;
7.             else if (root->val < val) root = root->right;
8.             else return root;
9.         }
10.         return nullptr;
11.     }
12. };

复制代码

Leetcode 98-验证二叉搜索树

题目形貌

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

解题思路

要充分利用二叉搜索树的特性，要使用中序遍历（左中右），在如许的遍历序次下，遍历的值是逐渐递增的。
要注意二叉搜索树不仅仅是中节点的值大于左节点小于右节点，同时需要保证中节点的值大于左子树的全部值，小于右子树的全部值。

1. class Solution {
2. public:
3.     TreeNode* pre = nullptr;
4.     bool isValidBST(TreeNode* root) {
5.         if (root == nullptr)return true;
6.         bool left = isValidBST(root->left);
7.         if (pre != nullptr && root->val <= pre->val)return false;
8.         else pre = root;
9.         bool right = isValidBST(root->right);
10.         return left && right;
11.     }
12. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。