[LeetCode] 113. Path Sum II

【原题】 Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum. For example: Given the below binary tree and sum = 22,

          5
         / \
        4   8
       /   / \
      11  13  4
     /  \    / \
    7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]
]

【解释】 给定一颗二叉树和一个目标target,要求返回二叉树中从根节点到叶子结点的所有节点之和为target的路径。

【思路】 DFS的思想,若左右结点都遍历完之后,要将最后一个加入的结点删除,表示已经遍历过该节点所有的左右子女。

public class Solution {
    public void pathSumCore(List<List<Integer>> results, List<Integer> result,int sum,TreeNode root){
        if(root==null)
            return;
        result.add(root.val);
        if(sum==root.val&&root.left==null&&root.right==null){
            results.add(new ArrayList<>(result));
            //result.remove(result.size()-1);
            //return ;//这里若要返回的话, 必须加前面的删除前面加入的路径
        }else{
        if(root.left!=null)
            pathSumCore(results,result,sum-root.val,root.left);
         if(root.right!=null)
            pathSumCore(results,result,sum-root.val,root.right);
        }
        result.remove(result.size()-1);//删除该结点

    }
     public List<List<Integer>> pathSum(TreeNode root, int sum) {
         List<Integer> result=new ArrayList<Integer>();
         List<List<Integer>> results=new ArrayList<List<Integer>>();
         pathSumCore(results,result,sum,root);
         return results;
        }
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏F_Alex

数据结构与算法(八)-二叉树(斜二叉树、满二叉树、完全二叉树、线索二叉树)

前言:前面了解了树的概念和基本的存储结构类型及树的分类,而在树中应用最广泛的种类是二叉树

562
来自专栏肖洒的博客

数据结构笔记(二)

栈是限定仅在表尾进行插入和删除操作的线性表。 队列是只允许在一段进行插入操作、而在另一端进行删除操作的线性表。

823
来自专栏琯琯博客

PHP二叉树(三):红黑树

2644
来自专栏猿人谷

二叉树的遍历——递归和非递归

二 叉树是一种非常重要的数据结构,很多其它数据结构都是基于二叉树的基础演变而来的。对于二叉树,有前序、中序以及后序三种遍历方法。因为树的定义本身就是 递归定义...

1968
来自专栏日常分享

Java 通过先序中序序列生成二叉树

  二叉树的前序以及后续序列,以空格间隔每个元素,重构二叉树,最后输出二叉树的三种遍历方式的序列以验证。

1161
来自专栏用户画像

4.3.1 二叉树的遍历

所谓二叉树的遍历,是指按照某条搜索路径访问树中的每个结点,使得每个几点均被访问一次,而且仅被访问一次。

762
来自专栏Bingo的深度学习杂货店

Q110 Balanced Binary Tree

Given a binary tree, determine if it is height-balanced. For this problem, a hei...

2785
来自专栏编程坑太多

HashMap 源码解析

1182
来自专栏大闲人柴毛毛

剑指offer代码解析——面试题25二叉树中和为某一值的路径

题目:输入一棵二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。PS:从根结点开始,一直到叶子结点形式一条路径。 分析:要找出路径之和为指定整...

2765
来自专栏Android机动车

数据结构学习笔记——树(上)

之前一直介绍的是一对一的线性结构,可现实中还有多一对多的情况需要处理,这就是今天要介绍的一对多的数据结构——树。

752

扫码关注云+社区