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

相关文章

来自专栏武培轩的专栏

剑指Offer-反转链表

题目描述 输入一个链表,反转链表后,输出链表的所有元素。 思路 思路一: 迭代:将当前节点和下一节点保存起来,然后将当前节点反转。 思路二: 递归:利用递归走到...

2624
来自专栏算法修养

CodeForces 670C Cinema(排序,离散化)

C. Cinema time limit per test 2 seconds memory limit per test 256 megabyte...

3207
来自专栏技术碎碎念

LeetCode-1- Two Sum

Given an array of integers, return indices of the two numbers such that they add...

2768
来自专栏计算机视觉与深度学习基础

Leetcode 90 Subsets II

Given a collection of integers that might contain duplicates, nums, return all ...

1838
来自专栏数据结构与算法

Tour UVA - 1347

John Doe, a skilled pilot, enjoys traveling. While on vacation, he rents a small...

3255
来自专栏算法修养

ZOJ 3932 Deque and Balls

There are n balls, where the i-th ball is labeled as pi. You are going to put n ...

2215
来自专栏WD学习记录

LeetCode Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

651
来自专栏来自地球男人的部落格

[LeetCode] 39.Combination Sum

【原题】 Given a set of candidate numbers (C) (without duplicates) and a target ...

1857
来自专栏java工会

Java中List集合去除重复数据的方法

4.把list里的对象遍历一遍,用list.contain(),如果不存在就放入到另外一个list集合中

692
来自专栏xingoo, 一个梦想做发明家的程序员

链表之链式存储

优点: 1 空间存储方便,现用现申请 2 插入删除,只针对单一数据,不需要移动大量数据 缺点: 1 读取,插入,删除慢,需要从头查找,时间复杂度均为O(n) 数...

1819

扫码关注云+社区