草庐IT

【JS】112. 路径总和

PaturNax 2023-03-28 原文

112. 路径总和

代码

DFS

var hasPathSum = function(root, targetSum) {
    //找到没有根了，那么就说明这条路行不通
    if(!root){
        return false;
    }

    //既没有左节点，也没有右节点，则是叶子节点
    if(!root.left && !root.right){
        return root.val === targetSum; 
    }

    //递归
    return hasPathSum(root.left,targetSum-root.val) || hasPathSum(root.right,targetSum-root.val)
};

复杂度分析:

  • 时间复杂度：\(O(N)\),N是节点数
  • 空间复杂度:\(O(T)\),T是树节点的高度

BFS

队列1则保存节点
队列2用来存放节点到根节点的路径和

var hasPathSum = function(root, targetSum) {
    //过了叶子节点的情况，就是找不到符合的路径
    if(root == null){
        return false;
    }

    var queue1 = [root];
    var queue2 = [root.val];
    //当有节点可以继续拿来用时
    while(queue1.length !== 0){
        //出队列
        var node = queue1.shift();
        var rootVal=queue2.shift();
        //找到叶子节点，并且也符合目标值的情况
        if(node.left == null && node.right == null && rootVal == targetSum){
            return true;
        }
        //继续遍历左节点
        if(node.left){
            //记录往了左节点
            queue1.push(node.left);
            //记录走了后的值为多少
            queue2.push(node.left.val+rootVal);
        }
        //继续遍历右节点
        if(node.right){
            queue1.push(node.right);
            queue2.push(node.right.val+rootVal);
        }
    }
    return false;
};

复杂度分析:

  • 时间复杂度：\(O(N)\),N是节点数
  • 空间复杂度:\(O(N)\),N是树节点的节点数
112路径rootqueuetargetSum算法与数据结构

有关【JS】112. 路径总和的更多相关文章

  1. ruby-on-rails - Rails - 使用/自定义 URL : '/dashboard' 指定根路径 - 2

    如何使此根路径转到:“/dashboard”而不仅仅是http://example.com？root:to=>'dashboard#index',:constraints=>lambda{|req|!req.session[:user_id].blank?} 最佳答案 您可以通过以下方式实现:root:to=>redirect('/dashboard')match'/dashboard',:to=>"dashboard#index",:constraints=>lambda{|req|!req.session[:user_id].b

  2. ruby - 如何根据长度将路径数组转换为嵌套数组或散列 - 2

    我需要根据字符串路径的长度将字符串路径数组转换为符号、哈希和数组的数组给定以下数组:array=["info","services","about/company","about/history/part1","about/history/part2"]我想生成以下输出，对不同级别进行分组，根据级别的结构混合使用符号和对象。产生以下输出:[:info,:services,about:[:company,history:[:part1,:part2]]]#altsyntax[:info,:services,{:about=>[:company,{:history=>[:part1,:pa

  3. ruby-on-rails - 如何播种图像的路径？ - 2

    Organization和Image具有一对一的关系。Image有一个名为filename的列，它存储文件的路径。我在Assets管道中包含这样一个文件:app/assets/other/image.jpg。播种时如何包含此文件的路径？我已经在我的种子文件中尝试过:@organization=...@organization.image.create!(filename:File.open('app/assets/other/image.jpg'))#Ialsotried:#@organization.image.create!(filename:'app/assets/other/i

  4. ruby-on-rails - Assets 管道损坏 : Not compiling on the fly css and js files - 2

    我开始了一个新的Rails3.2.5项目，Assets管道不再工作了。CSS和Javascript文件不再编译。这是尝试生成Assets时日志的输出:StartedGET"/assets/application.css?body=1"for127.0.0.1at2012-06-1623:59:11-0700Servedasset/application.css-200OK(0ms)[2012-06-1623:59:11]ERRORNoMethodError:undefinedmethod`each'fornil:NilClass/Users/greg/.rbenv/versions/1

  5. ruby-on-rails - Rails - 理解 application.js 和 application.css - 2

    rails新手。只是想了解\assests目录中的这两个文件。例如，application.js文件有如下行://=requirejquery//=requirejquery_ujs//=require_tree.我理解require_tree。只是将所有JS文件添加到当前目录中。根据上下文，我可以看出requirejquery添加了jQuery库。但是它从哪里得到这些jQuery库呢？我没有在我的Assets文件夹中看到任何jquery.js文件——或者直接在我的整个应用程序中没有看到任何jquery.js文件？同样，我正在按照一些说明安装TwitterBootstrap(http:

  6. Ruby 和指南针路径与 yeoman 项目 - 2

    我安装了ruby​​、yeoman，当我运行我的项目时，出现了这个错误:Warning:Running"compass:dist"(compass)taskWarning:YouneedtohaveRubyandCompassinstalledthistasktowork.Moreinfo:https://github.com/gruUse--forcetocontinue.Use--forcetocontinue.我有进入可变session目标的路径，但它不起作用。谁能帮帮我？ 最佳答案 我必须运行这个:geminstallcom

  7. 对象的 Ruby 方法查找路径 - 2

    是否有内置的Ruby方法或众所周知的库可以返回对象的整个方法查找链？Ruby查看一系列令人困惑的类(如thisquestion中所讨论)以查找与消息对应的实例方法，如果没有类响应消息，则调用接收方的method_missing。我将以下代码放在一起，但我确信它遗漏了某些情况或者它是否100%正确。请指出任何缺陷并指导我找到一些更好的代码(如果存在)。defmethod_lookup_chain(obj,result=[obj.singleton_class])ifobj.instance_of?Classreturnadd_modules(result)ifresult.last==B

  8. Ruby Arrays - 求对角线的总和 - 2

    以前没见过这个，但我想知道如何在Ruby中找到二维数组的两条对角线之和。假设您有一个简单的数组，包含3行和3列。array=[1,2,3,4,5,6,7,8,9]我可以通过使用将它分成三个一组array.each_slice(3).to_a现在是[1,2,3],[4,5,6],[7,8,9][1,2,3][4,5,6][7,8,9]在这种情况下，对角线是1+5+9=153+5+7=15所以总和为15+15=30我想我可以做类似的事情diagonal_sum=0foriin0..2forjin0..2diagonal_sum+=array[i][j]endend

  9. ruby-on-rails - rails 中的路径解析 - 2

    我正在寻找这样解析路由路径的方法:ActionController::Routing.new("post_path").parse#=>{:controller=>"posts",:action=>"index"}应该和url_for相反更新我发现:Whatistheoppositeofurl_forinRails?Afunctionthattakesapathandgeneratestheinterpretedroute?ActionController::Routing::Routes.recognize_path("/posts")所以现在我需要将posts_path转换为“/p

  10. node.js - 如何在 Travis CI 上的一个项目中运行 Node.js 和 Ruby 测试 - 2

    我有一个包含多个组件的存储库，其中大部分是用JavaScript(Node.js)编写的，一个是用Ruby(RubyonRails)编写的。我想要一个.travis.yml文件来触发一个运行每个组件的所有测试的构建。根据thisTravisCIGoogleGroupthread，目前还没有官方支持。我的目录结构是这样的:.├──构建服务器├──核心├──扩展├──网络应用├──流浪文件├──package.json├──.travis.yml└──生成文件我希望能够运行特定版本的Ruby(2.2.2)和Node.js(0.12.2)。我已经有了一个make目标，所以maketest在每

随机推荐