日本综合一区二区|亚洲中文天堂综合|日韩欧美自拍一区|男女精品天堂一区|欧美自拍第6页亚洲成人精品一区|亚洲黄色天堂一区二区成人|超碰91偷拍第一页|日韩av夜夜嗨中文字幕|久久蜜综合视频官网|精美人妻一区二区三区

本文轉(zhuǎn)載自微信公眾號「代碼隨想錄」，作者程序員Carl 。轉(zhuǎn)載本文請聯(lián)系代碼隨想錄公眾號。

左葉子之和

題目地址：https://leetcode-cn.com/problems/sum-of-left-leaves/

計算給定二叉樹的所有左葉子之和。

示例：

思路

首先要注意是判斷左葉子，不是二叉樹左側(cè)節(jié)點，所以不要上來想著層序遍歷。

因為題目中其實沒有說清楚左葉子究竟是什么節(jié)點，那么我來給出左葉子的明確定義：如果左節(jié)點不為空，且左節(jié)點沒有左右孩子，那么這個節(jié)點就是左葉子

大家思考一下如下圖中二叉樹，左葉子之和究竟是多少?

其實是0，因為這棵樹根本沒有左葉子!

那么判斷當前節(jié)點是不是左葉子是無法判斷的，必須要通過節(jié)點的父節(jié)點來判斷其左孩子是不是左葉子。

如果該節(jié)點的左節(jié)點不為空，該節(jié)點的左節(jié)點的左節(jié)點為空，該節(jié)點的左節(jié)點的右節(jié)點為空，則找到了一個左葉子，判斷代碼如下：

  
 
 
 

   
  
  
  
if (node->left != NULL && node->left->left == NULL && node->left->right == NULL) { 
   
  
  
  
    左葉子節(jié)點處理邏輯 
   
  
  
  
} 
  
 
 
 

遞歸法

遞歸的遍歷順序為后序遍歷(左右中)，是因為要通過遞歸函數(shù)的返回值來累加求取左葉子數(shù)值之和。。

遞歸三部曲：

1.確定遞歸函數(shù)的參數(shù)和返回值

判斷一個樹的左葉子節(jié)點之和，那么一定要傳入樹的根節(jié)點，遞歸函數(shù)的返回值為數(shù)值之和，所以為int

使用題目中給出的函數(shù)就可以了。

2.確定終止條件

依然是

  
 
 
 

   
  
  
  
if (root == NULL) return 0; 
  
 
 
 

3.確定單層遞歸的邏輯

當遇到左葉子節(jié)點的時候，記錄數(shù)值，然后通過遞歸求取左子樹左葉子之和，和 右子樹左葉子之和，相加便是整個樹的左葉子之和。

代碼如下：

  
 
 
 

   
  
  
  
int leftValue = sumOfLeftLeaves(root->left);    // 左 
   
  
  
  
int rightValue = sumOfLeftLeaves(root->right);  // 右 
   
  
  
  
                                                // 中 
   
  
  
  
int midValue = 0; 
   
  
  
  
if (root->left && !root->left->left && !root->left->right) { 
   
  
  
  
    midValue = root->left->val; 
   
  
  
  
} 
   
  
  
  
int sum = midValue + leftValue + rightValue; 
   
  
  
  
return sum; 
  
 
 
 

整體遞歸代碼如下：

  
 
 
 

   
  
  
  
class Solution { 
   
  
  
  
public: 
   
  
  
  
    int sumOfLeftLeaves(TreeNode* root) { 
   
  
  
  
        if (root == NULL) return 0; 
   
  
  
  
 
   
  
  
  
        int leftValue = sumOfLeftLeaves(root->left);    // 左 
   
  
  
  
        int rightValue = sumOfLeftLeaves(root->right);  // 右 
   
  
  
  
                                                        // 中 
   
  
  
  
        int midValue = 0; 
   
  
  
  
        if (root->left && !root->left->left && !root->left->right) { // 中 
   
  
  
  
            midValue = root->left->val; 
   
  
  
  
        } 
   
  
  
  
        int sum = midValue + leftValue + rightValue; 
   
  
  
  
        return sum; 
   
  
  
  
    } 
   
  
  
  
}; 
  
 
 
 

以上代碼精簡之后如下：

  
 
 
 

   
  
  
  
class Solution { 
   
  
  
  
public: 
   
  
  
  
    int sumOfLeftLeaves(TreeNode* root) { 
   
  
  
  
        if (root == NULL) return 0; 
   
  
  
  
        int midValue = 0; 
   
  
  
  
        if (root->left != NULL && root->left->left == NULL && root->left->right == NULL) { 
   
  
  
  
            midValue = root->left->val; 
   
  
  
  
        } 
   
  
  
  
        return midValue + sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right); 
   
  
  
  
    } 
   
  
  
  
}; 
  
 
 
 

迭代法

本題迭代法使用前中后序都是可以的，只要把左葉子節(jié)點統(tǒng)計出來，就可以了，那么參考文章 二叉樹：聽說遞歸能做的，棧也能做!和二叉樹：迭代法統(tǒng)一寫法中的寫法，可以寫出一個前序遍歷的迭代法。

判斷條件都是一樣的，代碼如下：

  
 
 
 

   
  
  
  
class Solution { 
   
  
  
  
public: 
   
  
  
  
    int sumOfLeftLeaves(TreeNode* root) { 
   
  
  
  
        stack st; 
   
  
  
  
        if (root == NULL) return 0; 
   
  
  
  
        st.push(root); 
   
  
  
  
        int result = 0; 
   
  
  
  
        while (!st.empty()) { 
   
  
  
  
            TreeNode* node = st.top(); 
   
  
  
  
            st.pop(); 
   
  
  
  
            if (node->left != NULL && node->left->left == NULL && node->left->right == NULL) { 
   
  
  
  
                result += node->left->val; 
   
  
  
  
            } 
   
  
  
  
            if (node->right) st.push(node->right); 
   
  
  
  
            if (node->left) st.push(node->left); 
   
  
  
  
        } 
   
  
  
  
        return result; 
   
  
  
  
    } 
   
  
  
  
}; 
  
 
 
 

總結(jié)

這道題目要求左葉子之和，其實是比較繞的，因為不能判斷本節(jié)點是不是左葉子節(jié)點。

此時就要通過節(jié)點的父節(jié)點來判斷其左孩子是不是左葉子了。

平時我們解二叉樹的題目時，已經(jīng)習慣了通過節(jié)點的左右孩子判斷本節(jié)點的屬性，而本題我們要通過節(jié)點的父節(jié)點判斷本節(jié)點的屬性。

希望通過這道題目，可以擴展大家對二叉樹的解題思路。

其他語言版本

Java

遞歸

  
 
 
 

   
  
  
  
class Solution { 
   
  
  
  
    public int sumOfLeftLeaves(TreeNode root) { 
   
  
  
  
        if (root == null) return 0; 
   
  
  
  
        int leftValue = sumOfLeftLeaves(root.left);    // 左 
   
  
  
  
        int rightValue = sumOfLeftLeaves(root.right);  // 右 
   
  
  
  
                                                        
   
  
  
  
        int midValue = 0; 
   
  
  
  
        if (root.left != null && root.left.left == null && root.left.right == null) { // 中 
   
  
  
  
            midValue = root.left.val; 
   
  
  
  
        } 
   
  
  
  
        int sum = midValue + leftValue + rightValue; 
   
  
  
  
        return sum; 
   
  
  
  
    } 
   
  
  
  
} 
  
 
 
 

迭代

  
 
 
 

   
  
  
  
class Solution { 
   
  
  
  
    public int sumOfLeftLeaves(TreeNode root) { 
   
  
  
  
        if (root == null) return 0; 
   
  
  
  
        Stack stack = new Stack<> (); 
   
  
  
  
        stack.add(root); 
   
  
  
  
        int result = 0; 
   
  
  
  
        while (!stack.isEmpty()) { 
   
  
  
  
            TreeNode node = stack.pop(); 
   
  
  
  
            if (node.left != null && node.left.left == null && node.left.right == null) { 
   
  
  
  
                result += node.left.val; 
   
  
  
  
            } 
   
  
  
  
            if (node.right != null) stack.add(node.right); 
   
  
  
  
            if (node.left != null) stack.add(node.left); 
   
  
  
  
        } 
   
  
  
  
        return result; 
   
  
  
  
    } 
   
  
  
  
} 
  
 
 
 

Python

遞歸

  
 
 
 

   
  
  
  
class Solution: 
   
  
  
  
    def sumOfLeftLeaves(self, root: TreeNode) -> int: 
   
  
  
  
        if not root:  
   
  
  
  
            return 0 
   
  
  
  
         
   
  
  
  
        left_left_leaves_sum = self.sumOfLeftLeaves(root.left)  # 左 
   
  
  
  
        right_left_leaves_sum = self.sumOfLeftLeaves(root.right) # 右 
   
  
  
  
         
   
  
  
  
        cur_left_leaf_val = 0 
   
  
  
  
        if root.left and not root.left.left and not root.left.right:  
   
  
  
  
            cur_left_leaf_val = root.left.val  # 中 
   
  
  
  
             
   
  
  
  
        return cur_left_leaf_val + left_left_leaves_sum + right_left_leaves_sum 
  
 
 
 

迭代

  
 
 
 

   
  
  
  
class Solution: 
   
  
  
  
    def sumOfLeftLeaves(self, root: TreeNode) -> int: 
   
  
  
  
        """ 
   
  
  
  
        Idea: Each time check current node's left node.  
   
  
  
  
              If current node don't have one, skip it.  
   
  
  
  
        """ 
   
  
  
  
        stack = [] 
   
  
  
  
        if root:  
   
  
  
  
            stack.append(root) 
   
  
  
  
        res = 0 
   
  
  
  
         
   
  
  
  
        while stack:  
   
  
  
  
            # 每次都把當前節(jié)點的左節(jié)點加進去.  
   
  
  
  
            cur_node = stack.pop() 
   
  
  
  
            if cur_node.left and not cur_node.left.left and not cur_node.left.right:  
   
  
  
  
                res += cur_node.left.val 
   
  
  
  
                 
   
  
  
  
            if cur_node.left:  
   
  
  
  
                stack.append(cur_node.left) 
   
  
  
  
            if cur_node.right:  
   
  
  
  
                stack.append(cur_node.right) 
   
  
  
  
                 
   
  
  
  
        return res 
  
 
 
 

網(wǎng)頁名稱：做了這么多題目了，會求左葉子之和么？
網(wǎng)站鏈接：http://www.dlmjj.cn/article/djiicgi.html