devbox
正经夜光杯
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

代码随想录算法训练营：17/60

作者：正经夜光杯 | 2024-08-13 07:10:20

赞

踩

代码随想录算法训练营：17/60

非科班学习算法day17 | LeetCode654:最大二叉树 ，Leetcode617:合并二叉树 ，Leetcode700:二叉搜索树中的搜索，Leetcode98：验证二叉搜索树 

目录

介绍

一、基础概念补充：

1.二叉搜索树

二、LeetCode题目

1.LeetCode654:最大二叉树

题目解析

 2.Leetcode617:合并二叉树 

题目解析

3.Leetcode700:二叉搜索树中的搜索

题目解析

 

4.Leetcode98:验证二叉搜索树

题目解析

总结

介绍

包含LC的两道题目，还有相应概念的补充。

相关图解和更多版本：

代码随想录 (programmercarl.com)https://programmercarl.com/#%E6%9C%AC%E7%AB%99%E8%83%8C%E6%99%AF

一、基础概念补充：

1.二叉搜索树

二叉搜索树（Binary Search Tree，简称BST），又称有序二叉树或排序二叉树，是一种特殊的二叉树数据结构，它具有以下基本性质：

  1. 节点值的有序性：

    • 节点的左子树中所有节点的值都小于该节点的值。
    • 节点的右子树中所有节点的值都大于该节点的值。

  2. 唯一性：

    • 二叉搜索树中不允许有重复的节点值，即每个值都是唯一的。

  3. 递归定义：

    • 整个树要么为空，要么满足以上两个性质，并且左子树和右子树也必须分别是二叉搜索树。

由于这些性质，二叉搜索树支持一些非常高效的算法，例如：

  • 查找：从根节点开始，比较当前节点的值与目标值，根据大小关系决定向左子树还是右子树递归查找，时间复杂度在最佳情况下为O(log n)，最坏情况下为O(n)（当树退化为链表时）。

  • 插入：类似于查找，找到合适的位置后创建新节点插入，同时保持树的性质不变。

  • 删除：删除操作相对复杂，需要考虑被删除节点是否有子节点，以及如何调整树结构以保持二叉搜索树的性质，可能包括寻找前驱或后继节点来替代被删除节点。

相关性质还包括：

  • 中序遍历：二叉搜索树的中序遍历（左根右的顺序）会得到一个递增的序列，这是其有序性的直接体现，也是验证一个二叉树是否为二叉搜索树的一个简单方法。

  • 高度：二叉搜索树的高度与其节点插入的顺序有关，最坏情况下（每次插入的节点都是当前树的最大或最小值，导致树变为链式结构）高度为n，最好情况下接近log(n)。

为了优化性能，特别是减少高度，发展出了多种平衡二叉搜索树，如AVL树、红黑树等，它们通过额外的平衡条件和旋转操作来保证树的高度大致保持在对数级别，从而确保各种操作的平均时间复杂度为O(log n)。  

二、LeetCode题目

1.LeetCode654:最大二叉树

题目链接：654. 最大二叉树 - 力扣（LeetCode）

题目解析

       可以发现这道题和106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）非常相似，都是在所给的数组上做文章来构建树，那么具体如何操作呢。

        首先需要一个函数来寻找最大值

        然后根据信息创建节点

        之后根据最大值位置分割数组

        最后将得到的数组进行下一层递归

所以中止条件也应该是数组无法分割。

 c++代码如下：

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
  10.  * right(right) {}
  11.  * };
  12.  */
  13. class Solution {
  14. public:
  15.     TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
  16.         if (nums.size() == 1)
  17.             return new TreeNode(nums[0]);
  18.         // 寻找最大值 -----重置初始化！！！------
  19.         int max_val = 0;
  20.         int max_pos = 0;
  21.         for (int i = 0; i < nums.size(); ++i) {
  22.             if (nums[i] > max_val) {
  23.                 max_pos = i;
  24.                 max_val = nums[i];
  25.             }
  26.         }
  27.  
  28.         // 创建节点
  29.         TreeNode* root = new TreeNode(max_val);
  30.  
  31.         // 分割数组
  32.         // vector<int> left_nums = vector<int>(nums.begin(),
  33.         // nums.begin()+max_pos); vector<int> right_nums =
  34.         // vector<int>(nums.begin()+max_pos+1, nums.end());
  35.  
  36.         // 递归
  37.         if (max_pos > 0) {
  38.             vector<int> left_nums =
  39.                 vector<int>(nums.begin(), nums.begin() + max_pos);
  40.             root->left = constructMaximumBinaryTree(left_nums);
  41.         }
  42.         if (max_pos < nums.size() - 1) {
  43.             vector<int> right_nums =
  44.                 vector<int>(nums.begin() + max_pos + 1, nums.end());
  45.             root->right = constructMaximumBinaryTree(right_nums);
  46.         }
  47.         return root;
  48.     }
  49. };

注意点1：这里把寻找最大值函数放到里面了，尽量减少函数调用，同时还有个问题就是经过修改研究，尽量减少函数调用可以避免由于传入参量和调用函数之间发生冲突甚至未定义重定义等现象。

注意点2：注意在寻找最大值之前要把参数重新初始化，否则这种写法就会报错。

注意点3：关于中止条件，根据题目条件数组长度是一定大于等于1的，而且调试的时候发现用空来做，自己出了错，所以直接采用等于1时候，直接返回自身。

 2.Leetcode617:合并二叉树 

题目链接：617. 合并二叉树 - 力扣（LeetCode）

题目解析

       一开始考虑的特别复杂，其实根据题目描述，我们不需要完全新建一棵树，而且那样的空间消耗明显更多。所以进行分类讨论：

        左节点空，右节点不空，返回右节点

        右节点空，左节点不空，返回左节点

        左右节点都为空，返回空

        左右节点不为空，做加和操作，新建节点

        递归下一层的两个树对应位置

c++代码如下：

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
  10.  * right(right) {}
  11.  * };
  12.  */
  13. class Solution {
  14. public:
  15.     // 前序遍历
  16.     TreeNode* dfs(TreeNode* root1, TreeNode* root2) {
  17.         // 左空右回
  18.         if (root1 && !root2)
  19.             return root1;
  20.         // 右空左回
  21.         if (!root1 && root2)
  22.             return root2;
  23.         // 空返回
  24.         if (!root1 && !root2)
  25.             return nullptr;
  26.  
  27.         // 非空做加和
  28.         // 中
  29.         int sum_num = root1->val + root2->val;
  30.         // 创建新节点
  31.         TreeNode* new_root = new TreeNode(sum_num);
  32.         // 左
  33.         new_root->left = dfs(root1->left, root2->left);
  34.         // 右
  35.         new_root->right = dfs(root1->right, root2->right);
  36.  
  37.         // 返回二叉树的新根节点
  38.         return new_root;
  39.     }
  40.     TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
  41.         return dfs(root1, root2);
  42.     }
  43. };

3.Leetcode700:二叉搜索树中的搜索

题目链接：700. 二叉搜索树中的搜索 - 力扣（LeetCode）

题目解析

       二叉搜索树由于特性的存在，在搜索的时候，不用整棵树都搜索，每次判断之后，只需要选择一边递归。

C++代码如下：

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
  10.  * right(right) {}
  11.  * };
  12.  */
  13. class Solution {
  14. public:
  15.     TreeNode* searchBST(TreeNode* root, int val) {
  16.         if (!root)
  17.             return nullptr;
  18.         // 需要明确，写递归的时候是有条件的，不需要全部都搜索
  19.         if (root->val == val)
  20.             return root;
  21.  
  22.         if (root->val > val && root->left)
  23.             return searchBST(root->left, val);
  24.         if (root->val < val && root->right)
  25.             return searchBST(root->right, val);
  26.         return nullptr;
  27.     }
  28. };

注意点1：最后的返回值是null，而且递归函数如果有返回类型一定要用东西接住，要么return，要么赋值给其他变量。

 

4.Leetcode98:验证二叉搜索树

题目链接：98. 验证二叉搜索树 - 力扣（LeetCode）

题目解析

       最直接的做法就是根据二叉搜索树的性质进行中序遍历，然后检验结果是否是一个递增数组。

        优化思路就是，借助一个新的自定义指针来记录每一次在遍历过程中的节点，作为下一次递归的前一个结点，这样我们再次中序遍历，就可以直接比较前后两个节点的结果。最后返回值是左右两边共同检查的交。

C++代码如下：

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
  10.  * right(right) {}
  11.  * };
  12.  */
  13. class Solution {
  14. public:
  15.     vector<int> res;
  16.     vector<int> dis(TreeNode* root) {
  17.         if (!root)
  18.             return res;
  19.         dis(root->left);
  20.         res.push_back(root->val);
  21.         dis(root->right);
  22.         return res;
  23.     }
  24.  
  25.     bool isValidBST(TreeNode* root) {
  26.         dis(root);
  27.  
  28.         for (int i = 0; i < res.size() - 1; ++i) {
  29.             if (res[i] >= res[i + 1])
  30.                 return false;
  31.         }
  32.         return true;
  33.     }
  34. };

 记录指针中序遍历c++代码：

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
  10.  * right(right) {}
  11.  * };
  12.  */
  13. class Solution {
  14. public:
  15.     TreeNode* pre = nullptr;
  16.     bool isValidBST(TreeNode* root) {
  17.         // 现在要做的就是检索，然后
  18.         if (!root)
  19.             return true;
  20.  
  21.         // 还是中序遍历
  22.         bool left = isValidBST(root->left);
  23.         if (pre && pre->val >= root->val) //先写赋值，转头再想
  24.             return false;
  25.         pre = root;
  26.         bool right = isValidBST(root->right);
  27.         return left && right;
  28.     }
  29. };

总结


打卡第17天，坚持！！！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/正经夜光杯/article/detail/973749
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号