国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

[Leetcode-Tree] Path Sum I II III

notebin / 1131人閱讀

摘要:解題思路利用遞歸,對(duì)于每個(gè)根節(jié)點(diǎn),只要左子樹和右子樹中有一個(gè)滿足,就返回每次訪問一個(gè)節(jié)點(diǎn),就將該節(jié)點(diǎn)的作為新的進(jìn)行下一層的判斷。代碼解題思路本題的不同點(diǎn)是可以不從開始,不到結(jié)束。代碼當(dāng)前節(jié)點(diǎn)開始當(dāng)前節(jié)點(diǎn)左節(jié)點(diǎn)開始當(dāng)前節(jié)點(diǎn)右節(jié)點(diǎn)開始

Path Sum
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.

For example:
Given the below binary tree and sum = 22,

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

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

1.解題思路
利用遞歸,對(duì)于每個(gè)根節(jié)點(diǎn),只要左子樹和右子樹中有一個(gè)滿足,就返回true;
每次訪問一個(gè)節(jié)點(diǎn),就將sum-該節(jié)點(diǎn)的val,作為新的Sum進(jìn)行下一層的判斷。
直到葉子節(jié)點(diǎn),且sum與節(jié)點(diǎn)val相等,則表示存在這樣的path,返回true.
2.代碼

public class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root==null)return false;
        if(root.val==sum&&root.left==null&&root.right==null) return true;
        return hasPathSum(root.left,sum-root.val)||hasPathSum(root.right,sum-root.val);
        
    }
   
}

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

1.解題思路

本題是上一題的擴(kuò)展,需要列出所有滿足條件的path.我們只要在遞歸函數(shù)里添加List pre參數(shù)來存儲(chǔ)已經(jīng)生成的節(jié)點(diǎn)序列即可。

2.代碼

public class Solution {
    List> res=new ArrayList>();
    public List> pathSum(TreeNode root, int sum) {
        if(root==null) return res;
        helper(root,sum,new ArrayList());
        return res;
    }
    private void helper(TreeNode root, int sum,List pre){
        if(root==null) return;
        List cur=new ArrayList(pre);
        cur.add(root.val);
        if(root.left==null&&root.right==null&&sum==root.val){
            res.add(cur);
            return;
        }
       
        helper(root.left,sum-root.val,cur);
        helper(root.right,sum-root.val,cur);
    }
}

Path Sum III

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  
    5   -3
   /     
  3   2   11
 /    
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

1.解題思路

本題的不同點(diǎn)是path可以不從root開始,不到leaf結(jié)束。但由于可以存在負(fù)數(shù)節(jié)點(diǎn),所以沒法通過比較大小來縮進(jìn)節(jié)點(diǎn),所以我們就只能考慮從每一個(gè)節(jié)點(diǎn)開始的情況。

2.代碼

public class Solution {
    public int pathSum(TreeNode root, int sum) {
        if(root==null) return 0;
        //helper(root,sum) 當(dāng)前節(jié)點(diǎn)開始
        //pathSum(root.left,sum) 當(dāng)前節(jié)點(diǎn)左節(jié)點(diǎn)開始
        //pathSum(root.right,sum) 當(dāng)前節(jié)點(diǎn)右節(jié)點(diǎn)開始
        return helper(root,sum)+pathSum(root.left,sum)+pathSum(root.right,sum);
       
    }
    private int helper(TreeNode root,int sum){
       if(root==null) return 0;
       int count=0;
       if(root.val==sum) count++;
       return count+helper(root.left,sum-root.val)+helper(root.right,sum-root.val);
    }
}

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

轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/69805.html

相關(guān)文章

  • [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...

    張金寶 評(píng)論0 收藏0
  • [Leetcode] Path Sum I & II & III 路徑和1,2,3

    摘要:只要我們能夠有一個(gè)以某一中間路徑和為的哈希表,就可以隨時(shí)判斷某一節(jié)點(diǎn)能否和之前路徑相加成為目標(biāo)值。 最新更新請(qǐng)見: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 評(píng)論0 收藏0
  • 前端 | 每天一個(gè) LeetCode

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

    張漢慶 評(píng)論0 收藏0
  • [LeetCode] Combination Sum III | Combination Sum I

    摘要:此時(shí),若也正好減小為,說明當(dāng)前集合是正解,加入數(shù)組。兩個(gè)無法得到正解的情況是在為,而不為時(shí),當(dāng)然已經(jīng)無法得到正解,。在不為而卻已經(jīng)小于等于的情況下,此時(shí)仍要加入其它數(shù)以令為,而要加入的數(shù)都是到的正整數(shù),所以已無法滿足令為的條件,。 Combination Sum I & II: link Combination Sum III Problem Find all possible com...

    leiyi 評(píng)論0 收藏0
  • [Leetcode-Tree] Sum Root to Leaf Numbers

    摘要:解題思路本題要求所有從根結(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑和,我們用遞歸實(shí)現(xiàn)。結(jié)束條件當(dāng)遇到葉子節(jié)點(diǎn)時(shí),直接結(jié)束,返回計(jì)算好的如果遇到空節(jié)點(diǎn),則返回?cái)?shù)值。 Sum Root to Leaf NumbersGiven a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a numbe...

    BigNerdCoding 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<