leetcode113. Path Sum II

Eirunye 發(fā)布于2019-08-15 10:51 / 1152人閱讀

摘要：題目要求從樹中找到所有符合條件的從根節(jié)點到葉節(jié)點路徑，條件即為樹上所有節(jié)點值的和等于目標值?？梢詤⒖歼@篇博客思路和代碼其實這里本質上的思路并沒有改變，還是采用深度優(yōu)先算法，采用自頂向下遞歸的方式將符合條件的結果放入結果集中。

題目要求

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]
]

從樹中找到所有符合條件的從根節(jié)點到葉節(jié)點路徑，條件即為樹上所有節(jié)點值的和等于目標值。
Path Sum I可以參考這篇博客

思路和代碼

其實這里本質上的思路并沒有改變，還是采用深度優(yōu)先算法，采用自頂向下遞歸的方式將符合條件的結果放入結果集中。

    public List> pathSum(TreeNode root, int sum) {
        List> result = new ArrayList>();
        pathSum(root, sum, new ArrayList(), result);
        return result;
    }
    
    public void pathSum(TreeNode root, int sum, List path, List> result){
        if(root==null) return;
        sum -= root.val;
        if(isLeaf(root) && sum==0){
            path.add(root.val);
            result.add(new ArrayList(path));
            path.remove(path.size()-1);
            return;
        }
        path.add(root.val);
        pathSum(root.left, sum, path, result);
        pathSum(root.right, sum, path, result);
        path.remove(path.size()-1);
        
        
    }
    
    private boolean isLeaf(TreeNode node){
        return node!=null && node.left==null && node.right==null;
    }

想要了解更多開發(fā)技術，面試教程以及互聯(lián)網(wǎng)公司內推，歡迎關注我的微信公眾號！將會不定期的發(fā)放福利哦~

云服務器 GPU云服務器 jQuery113發(fā)布 Leetcod LeetCode LeetCode_String

文章版權歸作者所有，未經(jīng)允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉載請注明本文地址：http://systransis.cn/yun/67384.html

[LeetCode] Path Sum (I & II & III)

摘要： 112. Path Sum Problem Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. Note: A leaf is a node...

張金寶 2019-08-19 11:09 評論0 收藏0
[Leetcode-Tree] Path Sum I II III

摘要：解題思路利用遞歸，對于每個根節(jié)點，只要左子樹和右子樹中有一個滿足，就返回每次訪問一個節(jié)點，就將該節(jié)點的作為新的進行下一層的判斷。代碼解題思路本題的不同點是可以不從開始，不到結束。代碼當前節(jié)點開始當前節(jié)點左節(jié)點開始當前節(jié)點右節(jié)點開始 Path SumGiven a binary tree and a sum, determine if the tree has a root-to-lea...

notebin 2019-08-16 10:26 評論0 收藏0
[Leetcode] Path Sum I & II & III 路徑和1,2,3

摘要：只要我們能夠有一個以某一中間路徑和為的哈希表，就可以隨時判斷某一節(jié)點能否和之前路徑相加成為目標值。最新更新請見：https://yanjia.me/zh/2019/01/... Path Sum I Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that addin...

caiyongji 2019-08-14 12:25 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經(jīng)到題，所以后面會調整自己，在刷算法與數(shù)據(jù)結構的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。一目錄不折騰的前端，和咸魚有什么區(qū)別...

tain335 2019-08-26 10:28 評論0 收藏0
前端 | 每天一個 LeetCode

摘要：在線網(wǎng)站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

張漢慶 2019-08-23 13:42 評論0 收藏0