[[416239]]

本文轉(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<TreeNode*> 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)習(xí)慣了通過節(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<TreeNode> 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