成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[Leetcode-Tree]Sum of Left Leaves

ashe / 744人閱讀

摘要：解題思路這個題目其實就是基于先序遍歷，用遞歸和非遞歸思想都可以。遞歸求所有左葉子節(jié)點的和，我們可以將其分解為左子樹的左葉子和右子樹的左葉子和遞歸結(jié)束條件找到左葉子節(jié)點，就可以返回該節(jié)點的。代碼非遞歸判斷是否為左葉子節(jié)點遞歸

Sum of Left Leaves
Find the sum of all left leaves in a given binary tree.

Example:

    3
   / 
  9  20
    /  
   15   7

There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.

1.解題思路

這個題目其實就是基于先序遍歷，用遞歸和非遞歸思想都可以。
1）非遞歸：
借助棧，在push節(jié)點的時候判斷是否是左葉子節(jié)點，如果是就累計進sum中。
2）遞歸：
求所有左葉子節(jié)點的和，我們可以將其分解為左子樹的左葉子和+右子樹的左葉子和
遞歸結(jié)束條件：找到左葉子節(jié)點，就可以返回該節(jié)點的val。

2.代碼

1） 非遞歸

public class Solution {
    Stack s=new Stack();
     int sum=0;
    public int sumOfLeftLeaves(TreeNode root) {
        if(root==null) return 0;
        pushLeft(root);
        while(!s.empty()){
            TreeNode node=s.pop();
            if(node.right!=null)
                pushLeft(node.right);
        }
        return sum;
    }
    private void pushLeft(TreeNode root){
        TreeNode node=root;
        while(node!=null){
            s.push(node);
            //判斷是否為左葉子節(jié)點
            if(node.left!=null&&node.left.left==null&&node.left.right==null)
                sum+=node.left.val;
            node=node.left;
            
        }
    }
}

2)遞歸

public class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if(root==null) return 0;
        int leftsum,rightsum;
        if(root.left!=null&&root.left.left==null&&root.left.right==null)
            leftsum=root.left.val;
        else leftsum=sumOfLeftLeaves(root.left);
        rightsum=sumOfLeftLeaves(root.right);
        return leftsum+rightsum;
    }
}

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

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/69802.html

相關(guān)文章

  • [Leetcode-Tree] Path Sum I II III

    摘要：解題思路利用遞歸，對于每個根節(jié)點，只要左子樹和右子樹中有一個滿足，就返回每次訪問一個節(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 評論0 收藏0

  • [Leetcode-Tree] Sum Root to Leaf Numbers

    摘要：解題思路本題要求所有從根結(jié)點到葉子節(jié)點的路徑和，我們用遞歸實現(xiàn)。結(jié)束條件當遇到葉子節(jié)點時，直接結(jié)束，返回計算好的如果遇到空節(jié)點，則返回數(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 評論0 收藏0

  • [LeetCode] 404. Sum of Left Leaves

    Problem Find the sum of all left leaves in a given binary tree. Example: 3 / 9 20 / 15 7 There are two left leaves in the binary tree, with values 9 and 15 respectively. Return ...

    Mr_zhang 評論0 收藏0

  • [Leetcode-Tree]Binary Tree Maximum Path Sum

    摘要：但是本題的難點在于，使用遞歸實現(xiàn)，但是前面的第四種情況不能作為遞歸函數(shù)的返回值，所以我們需要定義兩個值，代表單邊路徑的最大值，用于遞歸用于和回路的較大值。 Binary Tree Maximum Path SumGiven a binary tree, find the maximum path sum. For this problem, a path is defined as a...

    caige 評論0 收藏0

  • [Leetcode-Tree]Maximum / Minimum Depth of Binary T

    摘要：解題思路用遞歸實現(xiàn)很簡單，對于每個根節(jié)點，最大深度就等于左子樹的最大深度和右子樹的最大深度的較大值。解題思路本題的注意點在于如果某個根節(jié)點有一邊的子樹為空，那么它的深度就等于另一邊不為空的子樹的深度，其他的邏輯與上一題相同。 Maximum Depth of Binary TreeGiven a binary tree, find its maximum depth. The maxi...

    Thanatos 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<