devbox
小小林熬夜学编程
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Day17.一刷数据结构算法(C语言版) 654最大二叉树；617合并二叉树；700二叉搜索树中的搜索；98验证二叉搜索树

作者：小小林熬夜学编程 | 2024-04-29 03:42:10

赞

踩

Day17.一刷数据结构算法(C语言版) 654最大二叉树；617合并二叉树；700二叉搜索树中的搜索；98验证二叉搜索树

        又是破防的一天......

一.654最大二叉树

        又是构造二叉树，昨天大家刚刚做完 中序后序确定二叉树，今天做这个 应该会容易一些， 先看视频，好好体会一下 为什么构造二叉树都是 前序遍历 

        题目链接：最大二叉树

        文章讲解：代码随想录

 1.思路分析

        简单来说，二叉树构建过程如下：

        构造树一般采用的是前序遍历，因为先构造中间节点，然后递归构造左子树和右子树。 

        递归三部曲：

        1）确定递归函数的参数和返回值

        参数传入的是存放元素的数组以及左右边界索引，返回该数组构造的二叉树的头结点，返回类型是指向节点的指针。

struct TreeNode* traversal(int* nums, int left, int right)

         2）确定终止条件

        当左右边界相等或左右颠倒时，返回NULL。

  1. //若左边界大于右边界，返回NULL
  2.     if(left >= right)
  3.         return NULL;

        3）确定单层递归的逻辑

        第一步：先要找到数组中最大的值和对应的下标， 最大的值构造根节点，下标用来下一步分割数组。

  1. //找出数组中最大数坐标
  2.     int maxIndex = left;
  3.     int i;
  4.     for(i = left + 1; i < right; i++) {
  5.         if(nums[i] > nums[maxIndex])
  6.             maxIndex = i;
  7.     }
  8.     
  9.     //开辟结点
  10.     struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
  11.     //将结点的值设为最大数组数组元素
  12.     node->val = nums[maxIndex];

        第二步：最大值所在的下标左区间构造左子树。

node->left = traversal(nums, left, maxIndex);

        第三步：最大值所在的下标右区间构造右子树。

node->right = traversal(nums, maxIndex + 1, right);

2.代码详解

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     struct TreeNode *left;
  6.  *     struct TreeNode *right;
  7.  * };
  8.  */
  9. struct TreeNode* traversal(int* nums, int left, int right) {
  10.     //若左边界大于右边界，返回NULL
  11.     if(left >= right)
  12.         return NULL;
  13.     
  14.     //找出数组中最大数坐标
  15.     int maxIndex = left;
  16.     int i;
  17.     for(i = left + 1; i < right; i++) {
  18.         if(nums[i] > nums[maxIndex])
  19.             maxIndex = i;
  20.     }
  21.     
  22.     //开辟结点
  23.     struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
  24.     //将结点的值设为最大数组数组元素
  25.     node->val = nums[maxIndex];
  26.     //递归定义左孩子结点和右孩子结点
  27.     node->left = traversal(nums, left, maxIndex);
  28.     node->right = traversal(nums, maxIndex + 1, right);
  29.     return node;
  30. }
  31.  
  32. struct TreeNode* constructMaximumBinaryTree(int* nums, int numsSize){
  33.     return traversal(nums, 0, numsSize);
  34. }

 二.617合并二叉树

        这次是一起操作两个二叉树了， 估计大家也没一起操作过两个二叉树，也不知道该如何一起操作，可以看视频先理解一下。 优先掌握递归。

        题目链接：合并二叉树

        文章讲解：代码随想录

 1.思路分析

        其实和遍历一个树逻辑是一样的，只不过传入两个树的节点，同时操作。

        这道题用哪种遍历都可以，本人以前序为例。

        递归三部曲：

        1）确定递归函数的参数和返回值

        首先要合入两个二叉树，那么参数至少是要传入两个二叉树的根节点，返回值就是合并之后二叉树的根节点。 

struct TreeNode* mergeTrees(struct TreeNode* root1, struct TreeNode* root2)

        2）确定终止条件

        因为是传入了两个树，那么就有两个树遍历的节点root1 和 root2，如果root1 == NULL 了，两个树合并就应该是 root2 了（如果root2也为NULL也无所谓，合并之后就是NULL）。

        反过来如果root2 == NULL，那么两个数合并就是root1（如果root1也为NULL也无所谓，合并之后就是NULL）。

        代码如下：

  1. if (root1 == NULL) return root2; // 如果root1为空，合并之后就应该是root2
  2. if (root2 == NULL) return root1; // 如果root2为空，合并之后就应该是root1

         3）确定单层递归的逻辑

        单层递归的逻辑就比较好写了，这里我们重复利用一下root1这个树，root1就是合并之后树的根节点（就是修改了原来树的结构）。

        那么单层递归中，就要把两棵树的元素加到一起。

root->val=root1->val+root2->val;

        接下来root1 的左子树是：合并root1左子树root2左子树之后的左子树。

        root1 的右子树：是 合并 root1右子树 root2右子树之后的右子树。

        最终t1就是合并之后的根节点。

  1. root->left=mergeTrees(root1->left,root2->left);
  2. root->right=mergeTrees(root1->right,root2->right);
  3. return root;

 2.代码详解

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     struct TreeNode *left;
  6.  *     struct TreeNode *right;
  7.  * };
  8.  */
  9. struct TreeNode* mergeTrees(struct TreeNode* root1, struct TreeNode* root2) {
  10.     if(root1==NULL) return root2;
  11.     if(root2==NULL) return root1;
  12.     struct TreeNode* root=(struct TreeNode*)malloc(sizeof(struct TreeNode));
  13.     root->val=root1->val+root2->val;
  14.     root->left=mergeTrees(root1->left,root2->left);
  15.     root->right=mergeTrees(root1->right,root2->right);
  16.     return root;
  17. }

 三.700二叉搜索树中的搜索

        递归和迭代 都可以掌握以下，因为本题比较简单， 了解一下 二叉搜索树的特性

        题目链接：二叉搜索树中的搜索

        文章讲解: 代码随想录

        视频讲解：不愧是搜索树，这次搜索有方向了！| LeetCode：700.二叉搜索树中的搜索

1.思路分析

        本题，其实就是在二叉搜索树中搜索一个节点。那么我们来看看应该如何遍历。

        递归三部曲：

        1）确定递归函数的参数和返回值

        递归函数的参数传入的就是根节点和要搜索的数值，返回的就是以这个搜索数值所在的节点。

        代码如下：

struct TreeNode* searchBST(struct TreeNode* root, int val)

         2）确定终止条件

        如果root为空，或者找到这个数值了，就返回root节点。

if (root == NULL || root->val == val) return root;

        3） 确定单层递归的逻辑

        看看二叉搜索树的单层递归逻辑有何不同。

        因为二叉搜索树的节点是有序的，所以可以有方向的去搜索。

        如果root->val 大于val，搜索左子树，如果root->val 小于 val，就搜索右子树，最后如果都没有搜索到，就返回NULL。

  1. struct TreeNode* result = NULL;
  2. if (root->val > val) result = searchBST(root->left, val);
  3. if (root->val < val) result = searchBST(root->right, val);
  4. return result;

        很多人写递归函数的时候习惯直接写searchBST(root->right, val)，却忘了递归函数还有返回值。

        递归函数的返回值是什么? 是左子树如果搜索到了val，要将该节点返回。 如果不用一个变量将其接住，那么返回值不就没了。

        所以要result = searchBST(root->right, val);并在最后return result。

2.代码详解

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     struct TreeNode *left;
  6.  *     struct TreeNode *right;
  7.  * };
  8.  */
  9. struct TreeNode* searchBST(struct TreeNode* root, int val) {
  10.     if (root == NULL || root->val == val) return root;
  11.     struct TreeNode* result = NULL;
  12.     if (root->val > val) result = searchBST(root->left, val);
  13.     if (root->val < val) result = searchBST(root->right, val);
  14.     return result;
  15. }

 四.98验证二叉搜索树

        遇到 搜索树，一定想着中序遍历，这样才能利用上特性。 

        但本题是有陷阱的，可以自己先做一做，然后在看题解，看看自己是不是掉陷阱里了。这样理解的更深刻。

        题目链接：验证二叉搜索树

        文章讲解：代码随想录

        视频讲解：你对二叉搜索树了解的还不够！ | LeetCode：98.验证二叉搜索树

 1.思路分析

        要知道中序遍历下，输出的二叉搜索树节点的数值是有序序列。

        有了这个特性，验证二叉搜索树，就相当于变成了判断一个序列是不是递增的了。

        这道题目比较容易陷入两个陷阱：

  • 陷阱1

        不能单纯的比较左节点小于中间节点，右节点大于中间节点就完事了。

        我们要比较的是 左子树所有节点小于中间节点，右子树所有节点大于中间节点。

        例如： [10,5,15,null,null,6,20] 这个case：

 

        节点10大于左节点5，小于右节点15，但右子树里出现了一个6 这就不符合了！ 

  • 陷阱2

        样例中最小节点可能是int的最小值，如果这样使用最小的int来比较也是不行的。

        此时可以初始化比较元素为longlong的最小值。

        （不过本人写的代码并没有考虑longlong的情况，所以如果你比较顾虑，可以自行修改）

        递归三部曲：

        1）确定递归函数的参数和返回值

bool isValid(struct TreeNode* root,struct TreeNode** pre)

（悄悄话：其中，pre为用来记录前一个节点的指针的指针，我一开始本想当作全局变量放在函数前面。测试的时候没问题，但是提交的时候，面对{0}的输入，输出错误，也不知道怎么回事。如果你平时有认真看我的博客的话，你会发现我上一次也用了指针的指针来代替全局变量，错误的具体原因我也不太清楚，这也是我今天破防的原因。我回头再研究一下。我破防的另一个原因是，在第三题，我遍历的时候脑袋短路了，当时就是不明白为什么在最后要写返回值......）

        2）确定终止条件

        如果是空节点 是不是二叉搜索树呢？

        是的，二叉搜索树也可以为空！

if (root == NULL) return true;

        3）确定单层递归的逻辑

  1. bool left = isValid(root->left,pre);
  2.  
  3. if (*pre != NULL && (*pre)->val >= root->val) return false;
  4. *pre = root; // 记录前一个节点
  5.  
  6. bool right = isValid(root->right,pre);
  7. return left && right;

2.代码详解

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     struct TreeNode *left;
  6.  *     struct TreeNode *right;
  7.  * };
  8.  */
  9. bool isValid(struct TreeNode* root,struct TreeNode** pre) {
  10.     if (root == NULL) return true;
  11.     bool left = isValid(root->left,pre);
  12.  
  13.     if (*pre != NULL && (*pre)->val >= root->val) return false;
  14.     *pre = root; // 记录前一个节点
  16.     bool right = isValid(root->right,pre);
  17.     return left && right;
  18. }
  19. bool isValidBST(struct TreeNode* root){
  20.     struct TreeNode* pre = NULL;
  21.     return isValid(root,&pre);
  22. }

         如果你有问题或者有其他想法，欢迎评论区留言，大家可以一起探讨。

 

 

 

 

 

 

 

 

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

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

  

闽ICP备14008679号