文档章节

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

a_xianyu
 a_xianyu
发布于 2017/09/06 21:58
字数 196
阅读 20
收藏 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
[算法总结] 20 道题搞定 BAT 面试——二叉树

本文首发于我的个人博客:尾尾部落 0. 几个概念 完全二叉树:若二叉树的高度是h,除第h层之外,其他(1h-1)层的节点数都达到了最大个数,并且第h层的节点都连续的集中在最左边。想到点什么没...

繁著
09/04
0
0
编程题——21~30

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

thanatos_y
2016/07/22
1
0
[剑指offer] 二叉树中和为某一值的路径

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

繁著
07/01
0
0

没有更多内容

加载失败,请刷新页面

加载更多

IDEA 鼠标跳到下一行

敲代码时有时会出现这样的情况,鼠标在图中的位置,还需要手动将鼠标移动到这行的末尾然后再回车才能到新的一行。 用【Shift + Enter】,可以【IDEA新建一行,并且光标移到新行】...

karma123
16分钟前
3
0
在Kubernetes集群中部署ownCloud云盘系统

ownCloud ownCloud is a file sharing server that puts the control and security of your own data back into your hands. 参考 建立自己的共享云盘 - 使用ownCloud 远程访问家里机器的文件......

openthings
18分钟前
2
0
Python编写的以太坊虚拟机的新实现Py-EVM

Py-EVM是用Python编写的以太坊虚拟机的新实现。目前github上695个star,正在积极开发中,但正在通过以太坊/测试提供的测试套件快速推进。我们感谢有Vitalik和现有的PyEthereum代码,使得我们...

geek12345
20分钟前
1
0
(2)集成element-ui

(2)集成element-ui 1 安装element-ui依赖 cnpm install --save element-ui 2 按需引入 借助 babel-plugin-component,我们可以只引入需要的组件,以达到减小项目体积的目的。 首先,安装 ...

neumeng
25分钟前
2
0
linux下tree命令的用法解释

tree命令,主要功能是创建文件列表,将所有文件以树的形式列出来 linux下的tree就比较强大了,但一般系统并不自带这个命令,需要手动下载安装。 安装 : 1 yum -y install tree -a 显示所有文...

嘘嘘者
38分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部