[递归] 938. 二叉搜索树的范围和

悠悠 2021-12-09 00:05 112阅读 0赞

给定二叉搜索树的根结点 `root`，返回 `L` 和 `R`（含）之间的所有结点的值的和（即树中  X>=L&&X<=R 的X值的和）。

初始解法，全部遍历递归

class Solution \{  
public:  
    int rangeSumBST(TreeNode\* root, int L, int R) \{  
        int sum=0;  
        if(root->val>=L&&root->val<=R)  
        \{  
            sum+=root->val;  
        \}  
        if(root->left!=nullptr)  
        \{  
            sum+=rangeSumBST(root->left,L,R);  
        \}  
         if(root->right!=nullptr)  
        \{  
            sum+=rangeSumBST(root->right,L,R);  
        \}  
        return sum;  
    \}  
\};

另一种递归，时间反而比上面的长一点。

class Solution \{  
public:  
    int rangeSumBST(TreeNode\* root, int L, int R) \{  
        if(root==nullptr)  
        \{  
            return 0;  
        \}

if(root->val<L)  
        \{  
            return rangeSumBST(root->right,L,R);  
        \}  
        if(root->val>R)  
        \{  
            return rangeSumBST(root->left,L,R);  
        \}  
        return root->val+rangeSumBST(root->right,L,R)+rangeSumBST(root->left,L,R);  
    \}  
\};

发表评论取消回复

表情：

评论列表（有 0 条评论，112人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode 938.二叉搜索树的范围和（递归，BFS）

题目题目链接思路递归：根据二叉搜索树的性质（左子树的值都小于根节点，右子树的值都大于根节点）进行分类，如果当前根节点值为空，直接返回零；如果当前根节点值大于right，需...

快来打我*/ 2024年05月08日 06:15/ 0 赞/ 184 阅读

相关二叉搜索树的Java递归实现

目录前言二叉搜索树代码实现 add add代码 remove 被删除节点的两种类

╰半橙微兮°/ 2023年09月28日 13:42/ 0 赞/ 138 阅读

相关二叉树和递归

二叉树和递归文章目录二叉树和递归 1.二叉树的最大深度 2.二叉树的最小深度 3.反

曾经终败给现在/ 2023年07月04日 12:42/ 0 赞/ 62 阅读

相关 leetcode.938. 二叉搜索树的范围和

leetcode.938. 二叉搜索树的范围和深度优先搜索-官方 class Solution { public: int ra

r囧r小猫/ 2023年01月17日 06:26/ 0 赞/ 56 阅读

相关 LeetCode 938. 二叉搜索树的范围和

给定二叉搜索树的根结点 root，返回值位于范围 \[low, high\] 之间的所有结点的值的和。直接找即可： / Definition for a bin

快来打我*/ 2023年01月06日 15:54/ 0 赞/ 64 阅读

相关 700 二叉搜索树中的搜索（递归）

1. 问题描述：给定二叉搜索树（BST）的根节点和一个值。你需要在BST中找到节点值等于给定值的节点。返回以该节点为根的子树。如果节点不存在，则返回 NULL。例如，

旧城等待，/ 2022年09月03日 15:15/ 0 赞/ 184 阅读

相关 669 修剪二叉搜索树（递归修改）

1. 问题描述：给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在\[low, high\]中。修剪树

心已赠人/ 2022年09月02日 11:36/ 0 赞/ 296 阅读

相关数据结构之搜索二叉树递归&非递归

一.搜索二叉树的性质> 1). 每个节点都有一个作为搜索依据的关键码(key),所有节点的关键码互不相同。 2). 左子树上所有节点的关键码(key)都小于根节点的关键

曾经终败给现在/ 2022年07月16日 12:28/ 0 赞/ 213 阅读

相关二叉树递归非递归

include <iostream> include <string.h> include <stack> include <windows.

ゞ浴缸里的玫瑰/ 2022年07月14日 07:43/ 0 赞/ 222 阅读

相关 [递归] 938. 二叉搜索树的范围和

给定二叉搜索树的根结点 `root`，返回 `L` 和 `R`（含）之间的所有结点的值的和（即树中 X>=L&&X<=R 的X值的和）。初始解法，全部遍历递归 c

悠悠/ 2021年12月09日 00:05/ 0 赞/ 113 阅读