云社区 博客 博客详情
云社区 博客 博客详情

leetcode938(二叉搜索树的范围和)--C语言实现

Winniebear 发表于 2020-05-23 19:59:38 05-23 19:59
Winniebear 发表于 2020-05-23 19:59:38 2020/05/23
0
0

【摘要】 求:给定二叉搜索树的根结点 root,返回L和R(含)之间的所有结点的值的和。二叉搜索树保证具有唯一的值。 示例1:输入:root=[10,5,15,3,7,null,18],L=7,R=15输出:32示例 2:输入:root=[10,5,15,3,7,13,18,1,null,6],L=6,R=10输出:23 提示:树中的结点数量最多为 10000 个。最终的答案保证小于 2...

求:

给定二叉搜索树的根结点 root,返回 L 和 R(含)之间的所有结点的值的和。

二叉搜索树保证具有唯一的值。

 

示例 1:

输入:root = [10,5,15,3,7,null,18], L = 7, R = 15
输出:32
示例 2:

输入:root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10
输出:23
 

提示:

树中的结点数量最多为 10000 个。
最终的答案保证小于 2^31。

 

解:

思路:

很明确,如果节点值介于L和R之间,将它的值加入到范围和中。如果节点值小于L,在右子树中继续查找,如果节点值大于R,在左子树中继续查找。

递归调用,返回根节点的范围和。

我们也可以使用迭代实现,这里需要用到一个辅助数据结构:队列。首先将根节点入队列,然后从队列中依次弹出元素。弹出元素时,如果值介于L和R之间,更新范围和。并判断左右子树是否还有可能存在L和R之间的值,将相应的节点入队列。当整个队列为空时迭代完毕,返回结果。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

 

递归:

int  rangeSumBST( struct  TreeNode* root,  int  L,  int  R){
     if (root==NULL)   return   0 ;
     if (root->val < L){
         return  rangeSumBST(root->right,L,R);
    } else   if (root->val > R){
         return  rangeSumBST(root->left,L,R);
    } else {
         return  root->val + rangeSumBST(root->left,L,R) + rangeSumBST(root->right,L,R);
    }
}
 
迭代(这里用一下Java的轮子):
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class  Solution {
     public   int  rangeSumBST(TreeNode root,  int  L,  int  R) {
         int  ret =  0 ;
        Queue q =  new  LinkedList();
        q.add(root);
         while (!q.isEmpty()){
            TreeNode t = q.poll();
             if (t!=null){
                 if (t.val >=L && t.val <=R){
                    ret += t.val;
                }
                 if (t.val > L && t.left!=null){
                    q.add(t.left);
                }
                 if (t.val < R && t.right!=null){
                    q.add(t.right);
                }
            }
        }
         return  ret;
    }
}

文章来源: www.oschina.net,作者:拓拔北海,版权归原作者所有,如需转载,请联系作者。

原文链接:https://my.oschina.net/u/4469818/blog/4288506

登录后可下载附件,请登录或者注册

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:huaweicloud.bbs@huawei.com进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。
评论文章 //点赞 收藏 0
点赞
分享文章到微博
分享文章到朋友圈

评论 (0)


0/1000
评论

登录后可评论,请 登录注册

评论

您还没有写博客的权限!

温馨提示

您确认删除评论吗?

确定
取消
温馨提示

您确认删除评论吗?

删除操作无法恢复,请谨慎操作。

确定
取消
温馨提示

您确认删除博客吗?

确定
取消

确认删除

您确认删除博客吗?

确认删除

您确认删除评论吗?

温馨提示

登录超时或用户已下线,请重新登录!!!

确定
取消