- 浏览: 173206 次
- 性别:
- 来自: 济南
文章分类
最新评论
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
For example:
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
return
[
[5,4,11,2],
[5,8,4,5]
]
与Path Sum相比,这道题要求我们输出所有可能的结果,我们同样采用DFS,因为要输出所有可能的结果,我们用回溯法来记录,当找到符合条件的路径就记录下来,然后回溯,继续查找其它的路径。代码如下:
For example:
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
return
[
[5,4,11,2],
[5,8,4,5]
]
与Path Sum相比,这道题要求我们输出所有可能的结果,我们同样采用DFS,因为要输出所有可能的结果,我们用回溯法来记录,当找到符合条件的路径就记录下来,然后回溯,继续查找其它的路径。代码如下:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public List<List<Integer>> pathSum(TreeNode root, int sum) { List<List<Integer>> result = new ArrayList<List<Integer>>(); LinkedList<Integer> list = new LinkedList<Integer>(); if(root == null) return result; getPath(root, 0, sum, result, list); return result; } public void getPath(TreeNode root, int count, int sum, List<List<Integer>> result, LinkedList<Integer> list) { if(root == null) return; count += root.val; list.add(root.val); if(count == sum && root.left == null && root.right == null) { result.add(new LinkedList<Integer>(list)); list.removeLast(); return; } getPath(root.left, count, sum, result, list); getPath(root.right, count, sum, result, list); list.removeLast(); } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 224Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 222You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 339Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 330Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 448Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 508Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 427Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 617Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 426The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 384Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 514Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 528Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 366All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 858Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 879Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 552Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 598Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 761Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 731You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 626For a undirected graph with tre ...
相关推荐
113. Path Sum II Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum. Note: A leaf is a node with no children. Example: Given the below binary tree...
主要介绍了LeetCode -- Path Sum III分析及实现方法的相关资料,希望通过本文能帮助到大家,需要的朋友可以参考下
Path Sum II Binary Tree Maximum Path Sum Populating Next Right Pointers in Each Node Sum Root to Leaf Numbers LCA of Binary Tree 线段树 Range Sum Query - Mutable 排序 插入排序 Insertion Sort List 归并...
LeetCode — Path Sum III分析及实现方法 题目描述: You are given a binary tree in which each node contains an integer value. Find the number of paths that sum to a given value. The path does not need...
第 338 章力码解决方案 问题编号 标题 困难 C Java Ruby 338 中等的 [✓](/src/338 计数位/solution.c) 104 简单的 [✓](/src/104 ...II/solution.c) ...Path Sum II/solution.java) 258 简单的 [✓](/
命令行工具. 计算SHA1SUM,生成SHA1SUM文件.校验SHA1SUM文件. 如果安装了GnuPG,并在PATH中,对SHA1SUM进行明文签名(生成SHA1SUM.asc)或对其验证.
命令行工具. 计算SHA1SUM,生成SHA1SUM文件.校验SHA1SUM文件. 如果安装了GnuPG,并在PATH中,对SHA1SUM进行明文签名(生成SHA1SUM.asc)或对其验证. 修正对一些SHA1SUM.asc不能识别的bug
多线程 leetcode 前言 每天刷点leetcode,基于java语言...Path Sum II Copy List with Random Pointer Building H2O Fizz Buzz Multithreaded hard Merge k Sorted Lists Reverse Nodes in k-Group Trapping Rain Water
leetcode 树节点二叉树最大路径和 ...max_sum = Integer . MIN_VALUE ; public int max_gain ( TreeNode node ) { if (node == null ) return 0 ; // max sum on the left and right sub-trees of node int lef
linux下使用md5sum递归生成整个目录的md5 今天要用md5sum操作目录,递归生成目录下所有文件的md5值,结果发现它不支持递归操作于是写了个php脚本处理下 代码: <?php $path ='/data/www/bbs/source'; $...
//将每一种可能性都放入set中,并依次与sum对比public int pathSum(TreeNode root, int mySum){//1.递归出口/
hm.put("sum",new Double(sum_dingdan)); }catch (Exception e){ System.out.println(e.getMessage()); bl=false; //System.out.println("false"); } return hm; } public void setPath(String...
训练模型:python3 ./run_seq2seq.py --model_name_or_path t5-base --do_train --do_eval -任务总结--train_file data / training_data.csv --validation_file data / testing_data.csv --output_dir ./tmp/tst-...
#!/usr/bin/ruby -w # require 'digest/md5' ...def dir_md5sum(path) md5s=Array.new if File.directory?(path) Dir.new(path).each do |file| next if file =~ /^\.+$/ file=#{path}/#{file}
java lru leetcode :ice_cream: LeetCode Kindem 的个人 LeetCode 题解仓库,欢迎交流学习。 下面的目录中 $number 题号代表经典 LeetCode 题目,$number.$number 题号表示 ...Sum ...Sum ...Sum ...Path Sum 73
要构建自己的副本,请从sumtype存储库的根目录运行以下命令: path/to/adrdox/doc2 --genSearchIndex --genSource -o generated-docs src例子 import std.math: isClose;struct Fahrenheit { double degrees; }...
Path Sum Unique Paths Unique Paths II Longest Palindromic Substring Interleaving String Triangle Distinct Subsequences Decode Ways Palindrome Partitioning II Maximal Rectangle ###Recursion N-Queens N-...
matlab精度检验代码Kimia Path24 Kimia Path24是用于在数字病理学中进行图像分类和检索的数据集。...MD5SUM aeb54db89aaf28455e06770d20bd1307 数据集组织 数据按层次结构进行组织,如下所示。 | + -- scan0 | | |
['hpsum']['path']用于缓存HP SUM文件的路径,除非客户提供永久位置,否则为nil ['hpsum']['policy']['allow_reboot']默认为true ['hpsum']['inventory']['lastcheck']时间戳记 ['hpsum']['inventory']['interval'...
Max Sum. The following is an instance. (-2,11,-4,13,-5,-2) Shortest path in multistage graphs. Find the shortest path from 0 to 15 for the following graph. A multistage graph is a graph (1) G=...