[剑指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 条评论
登录 后参与评论

相关文章

来自专栏苦逼的码农

【漫画】以后在有面试官问你AVL树,你就把这篇文章扔给他。

例如,我现在想要查找数值为14的节点。由于二叉查找树的特性,我们可以很快着找到它,其过程如下:

21150
来自专栏彭湖湾的编程世界

【算法】论平衡二叉树(AVL)的正确种植方法

《算法(java)》                           — — Robert Sedgewick, Kevin Wayne

17320
来自专栏开发与安全

算法:二叉排序树的删除节点策略及其图形化(二叉树查找)

二叉排序树(BST,Binary Sort Tree)具有这样的性质:对于二叉树中的任意节点,如果它有左子树或右子树,则该节点的数据成员大于左子树所有节点的数据...

24390
来自专栏用户画像

PAT 1004

A family hierarchy is usually presented by a pedigree tree. Your job is to count...

7030
来自专栏武培轩的专栏

剑指Offer-二叉树中和为某一值的路径

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

35140
来自专栏菩提树下的杨过

spring cloud 学习(3) - feign入门

默认情况下,spring-boot的redis自动配置,只能注册一个StringRedisTemplate实例,如果希望注入多个,比如:1个读写database...

21380
来自专栏kevindroid

leetcode257 Binary Tree Paths

16050
来自专栏编程微刊

一个简易的选择小时(时分秒)的插件

34110
来自专栏武培轩的专栏

剑指Offer-把二叉树打印成多行

package Tree; import java.util.ArrayList; import java.util.LinkedList; import ...

40640
来自专栏Micro_awake web

python二叉树递归算法之后序遍历,前序遍历,中序遍历

1 #!/usr/bin/env python 2 # -*- coding: utf-8 -*- 3 # @Date : 2016-11-18 0...

29950

扫码关注云+社区

领取腾讯云代金券