代码随想录算法训练营:21/60

非科班学习算法day21 | LeetCode669:修剪二叉搜索树 ,Leetcode108:将有序数组转换为二叉搜索树 ,Leetcode538:把二叉搜索树转换为累加树 


介绍

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

相关图解和更多版本:

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


二、LeetCode题目

1.LeetCode669:修剪二叉搜索树 

题目链接:669. 修剪二叉搜索树 - 力扣(LeetCode)

题目解析

       这道题第二次做一开始还是迷糊,其实本质还是删除节点,只不过我们需要直到,不能看到没在范围的就直接删除,因为其子树也是有大有小的,所以就要处理相应的节点。那就是在下限之下,向右边遍历;在上限之上,向左边遍历。同时对于节点的拼接处理就是去掉一半子树。思路想清楚代码看起来还是比较简洁。

 c++代码如下:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) 
    {
        if(!root) return nullptr;
        if(root->val<low)
        {
            return trimBST(root->right, low,high);
            
        }
        if(root->val >high)
        {
            return trimBST(root->left,low,high);
        }
        root->left = trimBST(root->left,low,high);
        root->right = trimBST(root->right,low,high);
        return root;
    }
};

 2.Leetcode108:将有序数组转换为二叉搜索树 

题目链接:108. 将有序数组转换为二叉搜索树 - 力扣(LeetCode)

题目解析

        一开始还在想是不是需要将奇偶分类,实际上没有必要,因为有平衡的要求也不用慌,因为最中间的两个值,用左边和右边构造是一样的。这里就采用中间左边构造的形式。

        需要理清思路:每层选取最中间的数作为根节点,有点像之前根据遍历顺序构造数的做法。想清楚这个之后,代码才能好写起来。

 C++代码如下:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* sorted(vector<int>& nums, int left, int right) {
        if(left>right) return nullptr;
        int mid = left + (right - left) / 2;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = sorted(nums, left, mid - 1);
        root->right = sorted(nums, mid + 1, right);
        return root;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return sorted(nums, 0, nums.size() - 1);
    }
};

 注意点:因为要整个遍历,且返回值是作为对应根节点的孩子节点接住的!所以直接用root->left

3.Leetcode538:把二叉搜索树转换为累加树

题目链接:538. 把二叉搜索树转换为累加树 - 力扣(LeetCode)

题目解析

          一眼看上去也是构造树,不过这道题不需要动节点,只需要返回节点的值进行运算就可以,这里也是用回溯的思想。先遍历右边将右边的值返回,中做处理,就是相加,最后遍历左边。这样就符合了累加树的计算方法     

C++代码如下:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
class Solution {
public:
    // 尝试右中左遍历
    int sum = 0;
    TreeNode* convertBST(TreeNode* root) {
        if (!root)
            return nullptr;

        convertBST(root->right);
        sum += root->val;
        root->val = sum;
        convertBST(root->left);
        return root;
    }
};

注意点1:只是提供了一种新的思路,面对二叉树要灵活,把已经做过的看看能不能用上。

 

总结


补打卡第21天,坚持!!!

相关推荐

  1. 代码随想算法训练29期Day25|LeetCode 216,17

    2024-07-09 17:38:10       40 阅读
  2. 代码随想算法训练

    2024-07-09 17:38:10       41 阅读
  3. 代码随想算法训练

    2024-07-09 17:38:10       41 阅读
  4. 代码随想算法训练总结

    2024-07-09 17:38:10       31 阅读
  5. 代码随想算法训练总结

    2024-07-09 17:38:10       25 阅读
  6. 代码随想算法训练总结

    2024-07-09 17:38:10       23 阅读

最近更新

  1. 前端部署后提示用户刷新页面

    2024-07-09 17:38:10       0 阅读
  2. 编写测试用例:策略、技巧与最佳实践

    2024-07-09 17:38:10       0 阅读
  3. 自动化测试的艺术:Xcode中GUI测试的全面指南

    2024-07-09 17:38:10       0 阅读
  4. C++基础语法:STL之容器(6)--序列容器中的forward_list

    2024-07-09 17:38:10       0 阅读
  5. MongoDB Map-Reduce 简介

    2024-07-09 17:38:10       0 阅读
  6. 【SpringBoot】第3章 SpringBoot的系统配置

    2024-07-09 17:38:10       0 阅读
  7. Python中with 关键字、tell() 和 seek() 方法

    2024-07-09 17:38:10       0 阅读
  8. 初识数据结构中的“栈”

    2024-07-09 17:38:10       0 阅读
  9. 44、PHP 实现数据流中的中位数(含源码)

    2024-07-09 17:38:10       0 阅读

热门阅读

  1. Vue3 对于内嵌Iframe组件进行缓存

    2024-07-09 17:38:10       4 阅读
  2. Kafka 面试题指南

    2024-07-09 17:38:10       9 阅读
  3. vue3 插件

    2024-07-09 17:38:10       6 阅读
  4. 【PyQt5】

    2024-07-09 17:38:10       5 阅读
  5. 为啥AI要卷应用?

    2024-07-09 17:38:10       4 阅读