目錄

目前成都創新互聯已為1000多家的企業提供了網站建設、域名、虛擬空間、網站托管、服務器租用、企業網站設計、東鄉網站維護等服務，公司將堅持客戶導向、應用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協力一起成長，共同發展。

問題描述：

實現代碼與解析：

遞歸（后序）：

原理思路：

迭代（先序）：

原理思路：

---

問題描述：

給定二叉樹的根節點?root，返回所有左葉子之和。

示例 1：

輸入: root = [3,9,20,null,null,15,7] 
輸出: 24 
解釋: 在這個二叉樹中，有兩個左葉子，分別是 9 和 15，所以返回 24

示例?2:

輸入: root = [1]
輸出: 0

實現代碼與解析： 遞歸（后序）：

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

也可以這樣寫：

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) 
    {
        if(root==NULL) return 0;
        int leftValue=sumOfLeftLeaves(root->left);
        if(root->left&&root->left->left==NULL&&root->left->right==NULL) left=root->left->val;//記錄左葉子結點的值
        int rightValue=sumOfLeftLeaves(root->right);
        return leftValue+rightValue;
    }
};

其實就是把判斷左子樹為左葉子結點的步驟放在了中序上了而已，因為在中序判斷左子樹為左葉子結點的話，說明從左子樹返回的值一定為0，那么我們直接在父結點給leftValue賦值即可，減少了一個變量而已，沒什么區別。返回上一層的操作都還是在后序位置上。

精簡版：

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

原理思路：

? 我們先要明白左葉子結點是什么？并不是左側的結點，而是作為左孩子的葉子結點，如下圖：

? 因為我們要搜集的是左葉子結點，在遍歷到所指向結點時，只能判斷該結點是否為葉子結點，而不能判斷是左葉子結點還是右葉子結點，所以我們要在父結點的時候就開始判斷左子樹是否為左葉子結點，大家可以跟著代碼模擬著走一遍，題不難，但是有點繞。

迭代（先序）：

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

原理思路：

用迭代法還是比較簡單的，就是在原有的遍歷代碼（前中后序都可）上添加一下判斷是否為左葉子結點的代碼而已：

if(temp->left&&temp->left->left==NULL&&temp->left->right==NULL)
{
    result+=temp->left->val;
}

比較簡單和容易理解，就不詳細解析了。

你是否還在尋找穩定的海外服務器提供商？創新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統配攻擊溯源，準確流量調度確保服務器高可用性，企業級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

分享名稱：Leetcode：404.左葉子之和（C++）-創新互聯
轉載源于：http://www.yijiale78.com/article40/ddcoeo.html

成都網站建設公司_創新互聯，為您提供品牌網站制作、Google、商城網站、電子商務、定制網站、網站維護

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯