日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時(shí)間：8:30-17:00
你可能遇到了下面的問(wèn)題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營(yíng)銷解決方案
做了這么多題目了，會(huì)求左葉子之和么？

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

左葉子之和

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

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

示例：

思路

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

因?yàn)轭}目中其實(shí)沒(méi)有說(shuō)清楚左葉子究竟是什么節(jié)點(diǎn)，那么我來(lái)給出左葉子的明確定義：如果左節(jié)點(diǎn)不為空，且左節(jié)點(diǎn)沒(méi)有左右孩子，那么這個(gè)節(jié)點(diǎn)就是左葉子

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

其實(shí)是0，因?yàn)檫@棵樹根本沒(méi)有左葉子!

那么判斷當(dāng)前節(jié)點(diǎn)是不是左葉子是無(wú)法判斷的，必須要通過(guò)節(jié)點(diǎn)的父節(jié)點(diǎn)來(lái)判斷其左孩子是不是左葉子。

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

  
 
 
 
    
   
  
  
  
  1. if (node->left != NULL && node->left->left == NULL && node->left->right == NULL) { 
    2. 
   
  
  
  
  2.     左葉子節(jié)點(diǎn)處理邏輯 
    3. 
   
  
  
  
  3. } 
    4.

遞歸法

遞歸的遍歷順序?yàn)楹笮虮闅v(左右中)，是因?yàn)橐ㄟ^(guò)遞歸函數(shù)的返回值來(lái)累加求取左葉子數(shù)值之和。。

遞歸三部曲：

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

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

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

2.確定終止條件

依然是

  
 
 
 
    
   
  
  
  
  1. if (root == NULL) return 0; 
    2.

3.確定單層遞歸的邏輯

當(dāng)遇到左葉子節(jié)點(diǎn)的時(shí)候，記錄數(shù)值，然后通過(guò)遞歸求取左子樹左葉子之和，和 右子樹左葉子之和，相加便是整個(gè)樹的左葉子之和。

代碼如下：

  
 
 
 
    
   
  
  
  
  1. int leftValue = sumOfLeftLeaves(root->left);    // 左 
    2. 
   
  
  
  
  2. int rightValue = sumOfLeftLeaves(root->right);  // 右 
    3. 
   
  
  
  
  3.                                                 // 中 
    4. 
   
  
  
  
  4. int midValue = 0; 
    5. 
   
  
  
  
  5. if (root->left && !root->left->left && !root->left->right) { 
    6. 
   
  
  
  
  6.     midValue = root->left->val; 
    7. 
   
  
  
  
  7. } 
    8. 
   
  
  
  
  8. int sum = midValue + leftValue + rightValue; 
    9. 
   
  
  
  
  9. return sum; 
    10.

整體遞歸代碼如下：

  
 
 
 
    
   
  
  
  
  1. class Solution { 
    2. 
   
  
  
  
  2. public: 
    3. 
   
  
  
  
  3.     int sumOfLeftLeaves(TreeNode* root) { 
    4. 
   
  
  
  
  4.         if (root == NULL) return 0; 
    5. 
   
  
  
  
  5.  
    6. 
   
  
  
  
  6.         int leftValue = sumOfLeftLeaves(root->left);    // 左 
    7. 
   
  
  
  
  7.         int rightValue = sumOfLeftLeaves(root->right);  // 右 
    8. 
   
  
  
  
  8.                                                         // 中 
    9. 
   
  
  
  
  9.         int midValue = 0; 
    10. 
   
  
  
  
  10.         if (root->left && !root->left->left && !root->left->right) { // 中 
    11. 
   
  
  
  
  11.             midValue = root->left->val; 
    12. 
   
  
  
  
  12.         } 
    13. 
   
  
  
  
  13.         int sum = midValue + leftValue + rightValue; 
    14. 
   
  
  
  
  14.         return sum; 
    15. 
   
  
  
  
  15.     } 
    16. 
   
  
  
  
  16. }; 
    17.

以上代碼精簡(jiǎn)之后如下：

  
 
 
 
    
   
  
  
  
  1. class Solution { 
    2. 
   
  
  
  
  2. public: 
    3. 
   
  
  
  
  3.     int sumOfLeftLeaves(TreeNode* root) { 
    4. 
   
  
  
  
  4.         if (root == NULL) return 0; 
    5. 
   
  
  
  
  5.         int midValue = 0; 
    6. 
   
  
  
  
  6.         if (root->left != NULL && root->left->left == NULL && root->left->right == NULL) { 
    7. 
   
  
  
  
  7.             midValue = root->left->val; 
    8. 
   
  
  
  
  8.         } 
    9. 
   
  
  
  
  9.         return midValue + sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right); 
    10. 
   
  
  
  
  10.     } 
    11. 
   
  
  
  
  11. }; 
    12.

迭代法

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

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

  
 
 
 
    
   
  
  
  
  1. class Solution { 
    2. 
   
  
  
  
  2. public: 
    3. 
   
  
  
  
  3.     int sumOfLeftLeaves(TreeNode* root) { 
    4. 
   
  
  
  
  4.         stack st; 
    5. 
   
  
  
  
  5.         if (root == NULL) return 0; 
    6. 
   
  
  
  
  6.         st.push(root); 
    7. 
   
  
  
  
  7.         int result = 0; 
    8. 
   
  
  
  
  8.         while (!st.empty()) { 
    9. 
   
  
  
  
  9.             TreeNode* node = st.top(); 
    10. 
   
  
  
  
  10.             st.pop(); 
    11. 
   
  
  
  
  11.             if (node->left != NULL && node->left->left == NULL && node->left->right == NULL) { 
    12. 
   
  
  
  
  12.                 result += node->left->val; 
    13. 
   
  
  
  
  13.             } 
    14. 
   
  
  
  
  14.             if (node->right) st.push(node->right); 
    15. 
   
  
  
  
  15.             if (node->left) st.push(node->left); 
    16. 
   
  
  
  
  16.         } 
    17. 
   
  
  
  
  17.         return result; 
    18. 
   
  
  
  
  18.     } 
    19. 
   
  
  
  
  19. }; 
    20.

總結(jié)

這道題目要求左葉子之和，其實(shí)是比較繞的，因?yàn)椴荒芘袛啾竟?jié)點(diǎn)是不是左葉子節(jié)點(diǎn)。

此時(shí)就要通過(guò)節(jié)點(diǎn)的父節(jié)點(diǎn)來(lái)判斷其左孩子是不是左葉子了。

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

希望通過(guò)這道題目，可以擴(kuò)展大家對(duì)二叉樹的解題思路。

其他語(yǔ)言版本

Java

遞歸

  
 
 
 
    
   
  
  
  
  1. class Solution { 
    2. 
   
  
  
  
  2.     public int sumOfLeftLeaves(TreeNode root) { 
    3. 
   
  
  
  
  3.         if (root == null) return 0; 
    4. 
   
  
  
  
  4.         int leftValue = sumOfLeftLeaves(root.left);    // 左 
    5. 
   
  
  
  
  5.         int rightValue = sumOfLeftLeaves(root.right);  // 右 
    6. 
   
  
  
  
  6.                                                         
    7. 
   
  
  
  
  7.         int midValue = 0; 
    8. 
   
  
  
  
  8.         if (root.left != null && root.left.left == null && root.left.right == null) { // 中 
    9. 
   
  
  
  
  9.             midValue = root.left.val; 
    10. 
   
  
  
  
  10.         } 
    11. 
   
  
  
  
  11.         int sum = midValue + leftValue + rightValue; 
    12. 
   
  
  
  
  12.         return sum; 
    13. 
   
  
  
  
  13.     } 
    14. 
   
  
  
  
  14. } 
    15.

迭代

  
 
 
 
    
   
  
  
  
  1. class Solution { 
    2. 
   
  
  
  
  2.     public int sumOfLeftLeaves(TreeNode root) { 
    3. 
   
  
  
  
  3.         if (root == null) return 0; 
    4. 
   
  
  
  
  4.         Stack stack = new Stack<> (); 
    5. 
   
  
  
  
  5.         stack.add(root); 
    6. 
   
  
  
  
  6.         int result = 0; 
    7. 
   
  
  
  
  7.         while (!stack.isEmpty()) { 
    8. 
   
  
  
  
  8.             TreeNode node = stack.pop(); 
    9. 
   
  
  
  
  9.             if (node.left != null && node.left.left == null && node.left.right == null) { 
    10. 
   
  
  
  
  10.                 result += node.left.val; 
    11. 
   
  
  
  
  11.             } 
    12. 
   
  
  
  
  12.             if (node.right != null) stack.add(node.right); 
    13. 
   
  
  
  
  13.             if (node.left != null) stack.add(node.left); 
    14. 
   
  
  
  
  14.         } 
    15. 
   
  
  
  
  15.         return result; 
    16. 
   
  
  
  
  16.     } 
    17. 
   
  
  
  
  17. } 
    18.

Python

遞歸

  
 
 
 
    
   
  
  
  
  1. class Solution: 
    2. 
   
  
  
  
  2.     def sumOfLeftLeaves(self, root: TreeNode) -> int: 
    3. 
   
  
  
  
  3.         if not root:  
    4. 
   
  
  
  
  4.             return 0 
    5. 
   
  
  
  
  5.          
    6. 
   
  
  
  
  6.         left_left_leaves_sum = self.sumOfLeftLeaves(root.left)  # 左 
    7. 
   
  
  
  
  7.         right_left_leaves_sum = self.sumOfLeftLeaves(root.right) # 右 
    8. 
   
  
  
  
  8.          
    9. 
   
  
  
  
  9.         cur_left_leaf_val = 0 
    10. 
   
  
  
  
  10.         if root.left and not root.left.left and not root.left.right:  
    11. 
   
  
  
  
  11.             cur_left_leaf_val = root.left.val  # 中 
    12. 
   
  
  
  
  12.              
    13. 
   
  
  
  
  13.         return cur_left_leaf_val + left_left_leaves_sum + right_left_leaves_sum 
    14.

迭代

  
 
 
 
    
   
  
  
  
  1. class Solution: 
    2. 
   
  
  
  
  2.     def sumOfLeftLeaves(self, root: TreeNode) -> int: 
    3. 
   
  
  
  
  3.         """ 
    4. 
   
  
  
  
  4.         Idea: Each time check current node's left node.  
    5. 
   
  
  
  
  5.               If current node don't have one, skip it.  
    6. 
   
  
  
  
  6.         """ 
    7. 
   
  
  
  
  7.         stack = [] 
    8. 
   
  
  
  
  8.         if root:  
    9. 
   
  
  
  
  9.             stack.append(root) 
    10. 
   
  
  
  
  10.         res = 0 
    11. 
   
  
  
  
  11.          
    12. 
   
  
  
  
  12.         while stack:  
    13. 
   
  
  
  
  13.             # 每次都把當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)加進(jìn)去.  
    14. 
   
  
  
  
  14.             cur_node = stack.pop() 
    15. 
   
  
  
  
  15.             if cur_node.left and not cur_node.left.left and not cur_node.left.right:  
    16. 
   
  
  
  
  16.                 res += cur_node.left.val 
    17. 
   
  
  
  
  17.                  
    18. 
   
  
  
  
  18.             if cur_node.left:  
    19. 
   
  
  
  
  19.                 stack.append(cur_node.left) 
    20. 
   
  
  
  
  20.             if cur_node.right:  
    21. 
   
  
  
  
  21.                 stack.append(cur_node.right) 
    22. 
   
  
  
  
  22.                  
    23. 
   
  
  
  
  23.         return res 
    24.

新聞標(biāo)題：做了這么多題目了，會(huì)求左葉子之和么？
瀏覽地址：http://www.5511xx.com/article/djiicgi.html