[剑指offer] 二叉树中和为某一值的路径
题目描述
输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
解题思路
用前序遍历的方式访问到某一结点时,把该结点添加到路径上,并用目标值减去该节点的值。如果该结点为叶结点并且目标值减去该节点的值刚好为0,则当前的路径符合要求,我们把加入res数组中。如果当前结点不是叶结点,则继续访问它的子结点。当前结点访问结束后,递归函数将自动回到它的父结点。因此我们在函数退出之前要在路径上删除当前结点,以确保返回父结点时路径刚好是从根结点到父结点的路径。
参考代码
import java.util.ArrayList; /** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ public class Solution { ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer> >(); ArrayList<Integer> temp = new ArrayList<Integer>(); public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) { if(root == null) return res; target -= root.val; temp.add(root.val); if(target == 0 && root.left == null && root.right == null) res.add(new ArrayList<Integer>(temp)); else{ FindPath(root.left, target); FindPath(root.right, target); } temp.remove(temp.size()-1); return res; } }
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
习题 5: 更多的变量和打印
一、 简述 “格式化字符串(format string)” - 每一次你使用 ' ’ 或 " " 把一些文本引用起来,你就建立了一个字符串。 字符串是程序将信息展示给人的方式。 二、 代码 #!usr/bin/env python # -*- coding:utf-8 -*- # Author: xixihuang # Date : 2016/08/31 09:52 AM # Desc : 习题5:更多的变量与打印 # 键入更多的变量并且将它们打印出来。这次将使用一个叫“格式化字符串(format string)”的东西。 # 每一次使用“把一些文本引用起来,你就建立了一个字符串。字符串是程序将信息展示给人的方式。 # # # my_name = 'Zed A. Shaw' my_age = 35 # not a lie my_height = 74 # inches my_weight = 180 # lbs my_eyes = 'Blue' my_teeth = 'White' my_hair = 'Brown' print "Let's talk about %s." % my_...
- 下一篇
小型音乐播放器插件APlayer.js的简单使用例子
本篇博客将会给出一个小型音乐播放器插件APlayer.js的使用例子。关于APlayer.js的具体介绍和Github地址,可以参考: https://github.com/MoePlayer/APlayer 。 我们使用APlayer.js的方式为:cdn服务,其HTML标签为: <link href="https://cdn.bootcss.com/aplayer/1.10.1/APlayer.min.css" rel="stylesheet"> <script src="https://cdn.bootcss.com/aplayer/1.10.1/APlayer.min.js"></script> 下面将给出一个具体的例子,在这个例子中,我们展示的歌曲为孙燕姿的遇见,需要事先设置好这首歌的标题、演唱者、播放URL、封面图片链接、歌词。具体的HTML代码如下: <!DOCTYPE html> <html> <head> <link href="https://cdn.bootcss.com/a...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
-
Docker使用Oracle官方镜像安装(12C,18C,19C)
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- CentOS8编译安装MySQL8.0.19
- Docker快速安装Oracle11G,搭建oracle11g学习环境
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- MySQL8.0.19开启GTID主从同步CentOS8
- CentOS7,8上快速安装Gitea,搭建Git服务器
- Jdk安装(Linux,MacOS,Windows),包含三大操作系统的最全安装
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
推荐阅读
最新文章
- CentOS6,CentOS7官方镜像安装Oracle11G
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- 设置Eclipse缩进为4个空格,增强代码规范
- Mario游戏-低调大师作品
- MySQL8.0.19开启GTID主从同步CentOS8
- Windows10,CentOS7,CentOS8安装MongoDB4.0.16
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
- CentOS8编译安装MySQL8.0.19
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池