文档章节

二叉树中和为某数的所有路径

a_xianyu
 a_xianyu
发布于 2017/09/06 21:58
字数 196
阅读 16
收藏 0
点赞 0
评论 0

剑指offer上的一个题。

这里也有:http://www.lintcode.com/zh-cn/problem/binary-tree-path-sum/, 可以用来测试写的代码的正确性

给定一个二叉树,找出所有路径中各节点相加总和等于给定 目标值 的路径。

一个有效的路径,指的是从根节点到叶节点的路径。

样例

给定一个二叉树,和 目标值 = 5:

     1
    / \
   2   4
  / \
 2   3

返回:

[
  [1, 2, 2],
  [1, 4]
]

贴上一个很容易理解的代码:(忘了哪来的。。)

private ArrayList<ArrayList<Integer>> listAll = new ArrayList<ArrayList<Integer>>();
private ArrayList<Integer> list = new ArrayList<Integer>();
    
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
    if(root == null) {
        return listAll;
    }
    list.add(root.val);
    target -= root.val;
    if(target == 0 && root.left == null && root.right == null){
        listAll.add(new ArrayList<Integer>(list));
    }
    FindPath(root.left, target);
    FindPath(root.right, target);
    list.remove(list.size()-1);
    return listAll;
}

 

© 著作权归作者所有

共有 人打赏支持
a_xianyu
粉丝 0
博文 36
码字总数 18533
作品 0
哈尔滨
程序员
python剑指offer66题

二维数组的查找 替换空格 从头到尾打印链表 重建二叉树 用两个栈实现队列 选择数组中的最小数字 斐波那契数列 跳台阶 变态跳台阶 矩形覆盖 二进制中1的个数 数值的整数次方 调整数组顺序使奇...

lyy0905
06/03
0
0
算法知识梳理(12) - 二叉树算法第二部分

面试算法代码知识梳理系列 算法知识梳理(1) - 排序算法 算法知识梳理(2) - 字符串算法第一部分 算法知识梳理(3) - 字符串算法第二部分 算法知识梳理(4) - 数组第一部分 算法知识梳理(5) - 数...

泽毛
2017/12/21
0
0
编程题——21~30

二十一、包含min函数的栈 定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中,调 用min、push及pop的时间复杂度都是O(1)。 二十二、栈的压入、弹出序列 输入两...

thanatos_y
2016/07/22
1
0
数据结构之树

数据结构之树 目录: 二叉树的结构 二叉树的性质 二叉树的遍历 二叉树的特例 二叉树典型程序 树是一种编程中常常用到的一种数据结构,它的逻辑是:除了根结点之外每个结点只有一个父结点,根...

花开半夏qb
2016/11/29
0
0
[剑指offer] 二叉树中和为某一值的路径

题目描述 输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。 解题思路 用前序遍历的方式访...

繁著
07/01
0
0
二叉树算法积累(二叉树镜像/子树判断)

二叉树算法积累 存在二叉树A.B判断二叉树B是否是A的子树。 注意问题边界条件的控制。 A为空直接返回False.B为空A不为空直接返回true 先查找A中和B的根节点值相同的节点。 存在则继续递归A中当...

沧州宁少
2017/11/29
0
0
树/二叉树(哈夫曼树/红黑树)笔记

1.树是一种常用数据结构,它是非线性结构。 2.树中任一普通节点可以有0或者多个子节点,但只能有一个父节点。 根节点没有父节点,叶子节点没有子节点。 3.二叉树: 1)每个节点最多只能有两个...

6pker
2015/08/14
0
0
*【九度OJ1368】|【剑指offer25】二叉树中和为某一值的路径

题目描述: 输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。 输入: 每个测试案例包括n...

aqia358
2013/12/25
0
0
编程题——31~40

三十一、连续子数组的最大和 输入一个整数组,数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。 求所有子数组的和的最大值。要求时间复杂度为O(n)。 三十二、从1到n整数中...

thanatos_y
2016/07/26
13
0
Android 面试文档分享

一、概述 最近在准备面试的东西,整理了一些读书笔记分享给各位 百度网盘地址,大家可以自由下载,以下内容完全原创。 前两部分是对于一些 经典书籍的读书笔记 和 面试题,都是上学看书的时候...

泽毛
2017/11/10
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

keepalived配置高可用集群

Linux集群概述 根据功能划分为两大类:高可用和负载均衡 高可用集群通常为两台服务器,一台工作,另外一台作为冗余,当提供服务的机器宕机,冗余将接替继续提供服务 实现高可用的开源软件有:...

TaoXu
12分钟前
0
0
mysql联表批处理操作

1 概述 mysql中的单表增删改查操作,可以说是基本中的基本. 实际工作中,常常会遇到一些基本用法难以处理的数据操作,譬如遇到主从表甚至多级关联表的情况(如一些历史问题数据的批量处理),考虑到...

社哥
15分钟前
0
0
IntelliJ IDEA 详细图解最常用的配置,适合刚刚用的新人。

刚刚使用IntelliJ IDEA 编辑器的时候,会有很多设置,会方便以后的开发,磨刀不误砍柴工。 比如:设置文件字体大小,代码自动完成提示,版本管理,本地代码历史,自动导入包,修改注释,修改...

kim_o
30分钟前
0
0
Google Java编程风格指南

目录 前言 源文件基础 源文件结构 格式 命名约定 编程实践 Javadoc 后记 前言 这份文档是Google Java编程风格规范的完整定义。当且仅当一个Java源文件符合此文档中的规则, 我们才认为它符合...

niithub
32分钟前
0
0
java.net.MalformedURLException异常说明

1.异常片段 Java代码中,在进行URL url = new URL(urllink)操作时,提示以下异常信息,该类异常主要问题出在参数urllink上面。 异常片段1 java.net.MalformedURLException at java.ne...

lqlm
32分钟前
1
0
CentOS7修改mysql5.6字符集

解决办法:CentOS7下修改MySQL数据库字符编码为UTF-8,UTF-8包含全世界所有国家所需要的字符集,是国际编码。 具体操作如下: 1.进入MySQL [root@tianqi-01 ~]# mysql -uroot -p Enter passw...

河图再现
34分钟前
0
0
DevExpress v18.1新版亮点——WPF篇(一)

用户界面套包DevExpress v18.1日前终于正式发布,本站将以连载的形式为大家介绍各版本新增内容。本文将介绍了DevExpress WPF v18.1 的新功能,快来下载试用新版本!点击下载>> Accordion Co...

Miss_Hello_World
36分钟前
0
0
Rancher 2.0集群与工作负载告警

Rancher 2.0操作指南。本文将step by step演示如何使用Rancher 2.0中集成的告警功能,包括设置通知程序、设置集群级别以及工作负载级别的告警。 在Rancher 1.x时期,告警功能是很多Rancher用...

RancherLabs
41分钟前
1
0
Python中字符串拼接的N中方法

python拼接字符串一般有以下几种方法: ①直接通过(+)操作符拼接 s = 'Hello'+' '+'World'+'!'print(s) 输出结果:Hello World! 使用这种方式进行字符串连接的操作效率低下,因为python中...

木头释然
43分钟前
9
0
JAVA排序之归并排序

归并排序思路就是不停拆分数组,直到拆成一个一个元素,之后将拆出来的元素按照拆分顺序反过来的顺序合并,出现前边值大于后边值,则换位置,放入临时数组,最后将临时数组覆盖原数组. public stat...

勤奋的蚂蚁
54分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部