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

相关文章

来自专栏书山有路勤为径

二叉树-路径之和

给定一个二叉树与整数sum,找出所有从根节点到叶结点的路径,这些路径上的节点值累加和为sum。

532
来自专栏赵俊的Java专栏

排序链表转换为二分查找树

1805
来自专栏和蔼的张星的图像处理专栏

85. 在二叉查找树中插入节点常规操作

You can assume there is no duplicate values in this tree + node.

952
来自专栏有趣的Python

算法与数据结构(五)二叉搜索树

二叉搜索树 (Binary Search Tree) 核心是解决问题。高效解决问题。 查找问题 Searching Problem: 查找问题是计算机中非常重...

2816
来自专栏java闲聊

设计模式之建造者模式

525
来自专栏小樱的经验随笔

Vijos P1114 FBI树【DFS模拟,二叉树入门】

描述 我们可以把由“0”和“1”组成的字符串分为三类:全“0”串称为B串,全“1”串称为I串,既含“0”又含“1”的串则称为F串。 FBI树是一种二叉树1,它的...

2639
来自专栏WD学习记录

牛客网 二叉树的深度

输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。

571
来自专栏书山有路勤为径

二叉树转链表

给定一个二叉树,将该二叉树 就地(in-place)转换为单链表。单链表中节点顺序 为二叉树前序遍历顺序。(不额外开辟存储空间) LeetCode 114. ...

502
来自专栏kevindroid

leetcode257 Binary Tree Paths

1375
来自专栏武培轩的专栏

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

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

2894

扫码关注云+社区