【手把手带你刷LeetCode】——11.二叉搜索树的范围和（DFS）

HelKyle 发布于2021-11-11 16:55 / 895人阅读

摘要：大家简单看一下纯递归的解法原题二叉搜索树的范围和解法题目描述给定二叉搜索树的根结点，返回值位于范围之间的所有结点的值的和。

【前言】

今天是力扣打卡第11天！

感谢铁汁们的陪伴，一起加油鸭！！

在第9天的时候写过这道题的递归解题方法，其实DFS使用的解题思想就是递归，所以大同小异啦。大家简单看一下纯递归的解法：

https://blog.csdn.net/weixin_57544072/article/details/121196600?spm=1001.2014.3001.5502

原题：二叉搜索树的范围和（DFS解法）

题目描述：

给定二叉搜索树的根结点 root，返回值位于范围 [low, high] 之间的所有结点的值的和。

示例1：

输入：root = [10,5,15,3,7,null,18], low = 7, high = 15输出：32

示例2：

输入：root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10输出：23

题解：

全都在代码里头咯。

代码执行：

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     struct TreeNode *left; *     struct TreeNode *right; * }; */int rangeSumBST(struct TreeNode* root, int low, int high){    // //方法一：递归法    // //找边界    // if(root == NULL){    //     return 0;    // }    // //左子树    // int leftSum = rangeSumBST(root->left, low, high);    // //右子树    // int rightSum = rangeSumBST(root->right, low, high);    // int result = leftSum + rightSum;    // //判断根节点    // if(root->val >= low && root->val <= high){    //     result += root->val;    // }    // return result;    //方法二：DFS    //判断特殊情况    if(root == NULL){        return 0;    }    //如果根节点的值大于high，那么右子树不满足，此时只需要判断左子树    if(root->val > high){        return rangeSumBST(root->left, low, high);    }    //如果根节点的值小于low，那么左子树一定不满足，此时只需要判断右子树    if(root->val < low){        return rangeSumBST(root->right, low, high);    }    //否则如果根节点的值在low和high之间，那么三者都需要判断    return root->val + rangeSumBST(root->left, low, high) + rangeSumBST(root->right, low, high);}

复杂度分析：

时间复杂度：O(N), 取决于二叉搜索树的节点数；

空间复杂度：O(N)，取决于递归调用栈空间的开销。

总结：

今天是力扣打卡第11天！

时间很紧，博主和铁汁们一起坚持，加油！！

超融合服务器专线服务这篇文章手把手带你阅读Netty源码【附二叉树的遍历二叉树的存储二叉树的存储结构

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/123049.html

【手把手带你刷LeetCode】——15.剑指offer之不用加减乘除做加法（位运算）

摘要：前言今天是力扣打卡第天天天做递归做烦了，换换脑子，嘿嘿。原题不用加减乘除做加法题目描述写一个函数，求两个整数之和，要求在函数体内不得使用四则运算符号。补码的优势加法减法可以统一处理只有加法器。【前言】今天是力扣打卡第15天！天天做递归做烦了，换换脑子，嘿嘿。原题：不用加减...

QLQ 2021-11-15 11:38 评论0 收藏0
LeetCode 精选TOP面试题【51 ~ 100】

摘要：有效三角形的个数双指针最暴力的方法应该是三重循环枚举三个数字。总结本题和三数之和很像，都是三个数加和为某一个值。所以我们可以使用归并排序来解决这个问题。注意因为归并排序需要递归，所以空间复杂度为 ...

Clect 2021-11-15 11:38 评论0 收藏0
【手把手带你刷好题】——21.一道笔试题（非力扣）

摘要：前言今天是刷题打卡第天可能有铁汁会问，为什么变成刷好题，而不是刷了呢因为最近笔者遇到很多经典的笔试题，想着记录下来，方便大家和自己学习，所以今后笔者会在标题上注明是不是力扣题。【前言】今天是刷题打卡第21天！可能有铁汁会问，为什么变成刷好题，而不是刷LeetCode 了呢？因为...

骞讳护 2021-11-22 09:34 评论0 收藏0
力扣(LeetCode)124

题目地址：https://leetcode-cn.com/probl...题目描述：给定一个非空二叉树，返回其最大路径和。本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。示例 1: 输入: [1,2,3] 1 / 2 3 输出: 6 示例 2: 输入: [-10,9,20,nul...

geekidentity 2019-08-16 16:58 评论0 收藏0
LeetCode 145. 二叉树的后序遍历【c++/java详细题解】

摘要：样例如样例所示，该二叉树的后序遍历为，下面来讲解递归的做法。二叉树的后序遍历顺序为左右根，因此我们直接按照左子树右子树根节点的方式遍历这颗二叉树。具体过程如下对于二叉树中的当前节点将当前节点压入栈中，并记录到数组中。 ...

iamyoung001 2021-09-09 09:33 评论0 收藏0