Path Sum II 解答

时间:2022-12-31 10:12:03

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 解答的更多相关文章

  1. 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 ...

  2. 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 ...

  3. &lbrack;leetcode&rsqb;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 ...

  4. 【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 ...

  5. 32&period; Path Sum &amp&semi;&amp&semi; Path Sum II

    Path Sum OJ: https://oj.leetcode.com/problems/path-sum/ Given a binary tree and a sum, determine if ...

  6. LeetCode&colon; 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 ...

  7. &lbrack;LeetCode&num;110&comma; 112&comma; 113&rsqb;Balanced Binary Tree&comma; Path Sum&comma; Path Sum II

    Problem 1 [Balanced Binary Tree] Given a binary tree, determine if it is height-balanced. For this p ...

  8. Path Sum&comma;Path Sum II

    Path Sum Total Accepted: 81706 Total Submissions: 269391 Difficulty: Easy Given a binary tree and a ...

  9. LeetCode之&OpenCurlyDoubleQuote;树”:Path Sum &amp&semi;&amp&semi; Path Sum II

    Path Sum 题目链接 题目要求: Given a binary tree and a sum, determine if the tree has a root-to-leaf path suc ...

随机推荐

  1. 安装运行Hadoop

    1 准备环境 1.1 Ubuntu 或者 VMware Workstation Pro+Ubuntu 1.2 Jdk 1.3 eclipse 或其他开发工具(可选) 2 安装Hadoop 2.1 从h ...

  2. canvas简单图片处理&lpar;灰色处理&rpar;

    反色处理写的比较简单,灰色处理写了一些注释 <!DOCTYPE html> <html> <head> <meta charset="UTF-8&q ...

  3. String与InputStream互转的几种方法

    [java] view plain copy /** * 利用BufferedReader实现Inputstream转换成String <功能详细描述> * * @param in * @ ...

  4. 非 动态规划---LIS

    题目:一个序列有N个数:A[1],A[2],…,A[N],求出最长非降子序列的长度.(见动态规划---LIS) /* 题目:一个序列有N个数:A[1],A[2],…,A[N],求出最长非降子序列的长度 ...

  5. &lbrack;置顶&rsqb; HTML语义和前端架构

    关于语义学 语义学是研究符号和意义之间的关系以及它们表示的内容.在语言学中,则主要是研究符号(例如单词,短语或者语音)在语言中所表达的意义.而在前端开发时,语义学则更多的关注HTML元素,属性以及它的 ...

  6. PHP分页倒序时&comma;需要注意的问题

    PHP分页倒序请求,如果有新数据加入,下一页会出现重复数据 解决方案: 第一次查询时,给前端返回一个查询时间戳,下一次请求时,把时间戳带过来,只查询比这个时间戳小的数据

  7. 针对不同&period;NET版本的条件编译

    原理:查找项目目录下的 csproj 文件,解析它,找到节点TargetFrameworkVersion,判断.net版本

  8. Ubuntu18&period;04搭建nodejs环境

    首先安装sudo apt install curl 然后安装命令(当前最新版本是0.33.2,最新版本可以在https://github.com/creationix/nvm查看): curl -o- ...

  9. 【转帖】理解 Linux 的虚拟内存

    理解 Linux 的虚拟内存 https://www.cnblogs.com/zhenbianshu/p/10300769.html 段页式内存 文章了里面讲了 页表 没讲段表 记得最开始的时候 学习 ...

  10. cmd&sol;git设置alias提高效率

    cmd设置alias 在cmd或者git中有有些命令是比较长的,却需要频繁的使用,那么我们就可以设置alias来简化操作,无形中减少大量的宝贵时间,具体步骤如下. 第一步: 创建cmd_alias.b ...