Question
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]
]
Solution
Traditional way, use DFS and recursion.
/**
* 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>>();
List<Integer> prevList = new ArrayList<Integer>();
dfs(root, sum, result, prevList);
return result;
} private void dfs(TreeNode root, int target, List<List<Integer>> result, List<Integer> prevList) {
if (root == null)
return;
prevList.add(root.val); if (root.left == null && root.right == null) {
if (root.val == target)
result.add(new ArrayList<Integer>(prevList));
} else {
List<Integer> tmpList2 = new ArrayList<Integer>(prevList);
if (root.left != null)
dfs(root.left, target - root.val, result, prevList);
if (root.right != null)
dfs(root.right, target - root.val, result, tmpList2);
} }
}
Path Sum II 解答的更多相关文章
-
Leetcode 笔记 113 - Path Sum II
题目链接:Path Sum II | LeetCode OJ Given a binary tree and a sum, find all root-to-leaf paths where each ...
-
Path Sum II
Path Sum II Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals ...
-
[leetcode]Path Sum II
Path Sum II Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals ...
-
【leetcode】Path Sum II
Path Sum II Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals ...
-
32. Path Sum &;&; Path Sum II
Path Sum OJ: https://oj.leetcode.com/problems/path-sum/ Given a binary tree and a sum, determine if ...
-
LeetCode: Path Sum II 解题报告
Path Sum II Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals ...
-
[LeetCode#110, 112, 113]Balanced Binary Tree, Path Sum, Path Sum II
Problem 1 [Balanced Binary Tree] Given a binary tree, determine if it is height-balanced. For this p ...
-
Path Sum,Path Sum II
Path Sum Total Accepted: 81706 Total Submissions: 269391 Difficulty: Easy Given a binary tree and a ...
-
LeetCode之“树”:Path Sum &;&; Path Sum II
Path Sum 题目链接 题目要求: Given a binary tree and a sum, determine if the tree has a root-to-leaf path suc ...
随机推荐
-
安装运行Hadoop
1 准备环境 1.1 Ubuntu 或者 VMware Workstation Pro+Ubuntu 1.2 Jdk 1.3 eclipse 或其他开发工具(可选) 2 安装Hadoop 2.1 从h ...
-
canvas简单图片处理(灰色处理)
反色处理写的比较简单,灰色处理写了一些注释 <!DOCTYPE html> <html> <head> <meta charset="UTF-8&q ...
-
String与InputStream互转的几种方法
[java] view plain copy /** * 利用BufferedReader实现Inputstream转换成String <功能详细描述> * * @param in * @ ...
-
非 动态规划---LIS
题目:一个序列有N个数:A[1],A[2],…,A[N],求出最长非降子序列的长度.(见动态规划---LIS) /* 题目:一个序列有N个数:A[1],A[2],…,A[N],求出最长非降子序列的长度 ...
-
[置顶] HTML语义和前端架构
关于语义学 语义学是研究符号和意义之间的关系以及它们表示的内容.在语言学中,则主要是研究符号(例如单词,短语或者语音)在语言中所表达的意义.而在前端开发时,语义学则更多的关注HTML元素,属性以及它的 ...
-
PHP分页倒序时,需要注意的问题
PHP分页倒序请求,如果有新数据加入,下一页会出现重复数据 解决方案: 第一次查询时,给前端返回一个查询时间戳,下一次请求时,把时间戳带过来,只查询比这个时间戳小的数据
-
针对不同.NET版本的条件编译
原理:查找项目目录下的 csproj 文件,解析它,找到节点TargetFrameworkVersion,判断.net版本
-
Ubuntu18.04搭建nodejs环境
首先安装sudo apt install curl 然后安装命令(当前最新版本是0.33.2,最新版本可以在https://github.com/creationix/nvm查看): curl -o- ...
-
【转帖】理解 Linux 的虚拟内存
理解 Linux 的虚拟内存 https://www.cnblogs.com/zhenbianshu/p/10300769.html 段页式内存 文章了里面讲了 页表 没讲段表 记得最开始的时候 学习 ...
-
cmd/git设置alias提高效率
cmd设置alias 在cmd或者git中有有些命令是比较长的,却需要频繁的使用,那么我们就可以设置alias来简化操作,无形中减少大量的宝贵时间,具体步骤如下. 第一步: 创建cmd_alias.b ...