专栏首页尾尾部落[剑指offer] 二叉树中和为某一值的路径

[剑指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;
    }        
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Nginx 13: Permission denied 解决方案 Nginx 13: Permission denied 解决方案

    今天在用uwsgi+nginx在部署flask应用时,遇到502的错误,vim /var/log/nginx/error.log查看nginx的错误日志,提示如...

    尾尾部落
  • [剑指offer] 机器人的运动范围

    地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动,每一次只能向左,右,上,下四个方向移动一格,但是不能进入行坐标和列坐标的数位之和大于k的格子。...

    尾尾部落
  • [剑指offer] 数组中重复的数字

    在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复...

    尾尾部落
  • 程序员逻辑测试题(8)

    人们喜欢听对自己说“你好”、"请便",而不喜欢听"讨厌”、“恶心"这样的话。但是,一些人听到港台腔对自己说"你好"、"请便"也觉得讨厌。这说明,人们对话语的好恶...

    剑走天涯
  • 请你对Java中树的了解有多少?

    树 1200101班的学生信息表如图6.1所示,其中学生被分到了不同的学习小组,第一组组长是李华,组员有王丽、张阳、赵斌; 第二组组长是孙琪,组员有马丹; 第三...

    Java学习
  • Java - LDAP实现AD域单点登录

    断痕
  • 二叉树的建立和遍历

    二叉树:每个结点的子结点个数不大于2的树,叫做二叉树。 根结点:最顶部的那个结点叫做根结点,根结点是所有子结点的共同祖先。比如上图中的“7”结点就是根结点。 子...

    海天一树
  • ArrayList 源码解析

    size: 当前数组的大小(实时),类型 int,没有使用 volatile 修饰,非线程安全的

    飞翔的竹蜻蜓
  • Sentinel 流量控制 熔断降级 初探 原

        还记得之前写过一篇防雪崩利器:熔断器 Hystrix 的原理与使用https://my.oschina.net/u/3266761/blog/26544...

    chinotan
  • xiunoBBS(修罗)设置SMTP邮件的发送

    2017-08-2013:45:49 发表评论 346℃热度    前言 今天准备搭建一个论坛,用于用户交流。世纪搭建使用之后,决定使用xiuno BBS,界...

    timhbw

扫码关注云+社区

领取腾讯云代金券