找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1481|回复: 1
收起左侧

[米群网刷题小分队] 【LeetCode小分队】【Path Sum II】-【刷题第一弹 2014】

[复制链接]

24

主题

9

精华

602

积分

超级会员

Rank: 4

积分
602
发表于 10-23-2014 06:14 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 MengMa 于 12-7-2014 12:49 AM 编辑

快速通道:
https://oj.leetcode.com/problems/path-sum-ii/


Givena binary tree and a sum, find all root-to-leaf paths where each path's sumequals the given sum.

=========点击传送门查看所有题目哟========
                            汇总贴 传送门
==================================


思路:数的遍历,判断是否为叶子节点以及值是否为sum,需要注意的是只有在子树非空的时候才遍历


java代码:
  1. public void pathSum(TreeNode node, int sum,ArrayList<ArrayList<Integer>> rsts,ArrayList<Integer> path){
  2.         if(node==null)  return;
  3.         if(node.left==null&&node.right==null){
  4.             if(node.val==sum){
  5.             ArrayList<Integer> npath = new ArrayList<Integer>(path);
  6.             npath.add(node.val);
  7.             rsts.add(npath);
  8.             }
  9.             return;
  10.         }
  11.         path.add(node.val);
  12.         pathSum(node.left,sum-node.val,rsts,path);
  13.         pathSum(node.right,sum-node.val,rsts,path);
  14.         path.remove(path.size()-1);
  15.         return;
  16.     }
  17.     public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
  18.         ArrayList<ArrayList<Integer>> rsts= new ArrayList<ArrayList<Integer>>();
  19.         ArrayList<Integer> path = new ArrayList<Integer>();
  20.         if(root==null)  return rsts;
  21.         pathSum(root,sum,rsts,path);
  22.         return rsts;
  23. }
复制代码


复杂度:时间复杂度O(n),空间复杂度 O(h)


本帖被以下淘专辑推荐:

10

主题

7

精华

367

积分

高级会员

Rank: 3Rank: 3

积分
367
发表于 11-29-2014 12:03 PM | 显示全部楼层
  1. public class Solution {
  2.    
  3.     public List<List<Integer>> pathSum(TreeNode root, int sum) {
  4.         List<List<Integer>> rets=new ArrayList<List<Integer>>();
  5.         if(root==null) return rets;
  6.         
  7.         //leaf: if it is a valid path, add it to return list
  8.         if(root.left==null && root.right==null){
  9.             if(root.val==sum){
  10.                 List<Integer> list=new LinkedList<Integer>();
  11.                 list.add(0,root.val);
  12.                 rets.add(list);
  13.             }
  14.         }else{
  15.             //collection of lists from children are valid path, add itself to the path
  16.             List<List<Integer>> leftLists=pathSum(root.left,sum-root.val);
  17.             List<List<Integer>> rightLists=pathSum(root.right,sum-root.val);
  18.             leftLists.addAll(rightLists);
  19.             for(List list:leftLists){
  20.                 list.add(0,root.val);
  21.                 rets.add(list);
  22.             }
  23.         }
  24.         return rets;
  25.     }
  26. }
复制代码
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表