Leetcode：404.左葉子之和（C++）-創(chuàng)新互聯(lián)

目前成都創(chuàng)新互聯(lián)已為1000多家的企業(yè)提供了網(wǎng)站建設(shè)、域名、虛擬空間、網(wǎng)站托管、服務(wù)器租用、企業(yè)網(wǎng)站設(shè)計、東鄉(xiāng)網(wǎng)站維護(hù)等服務(wù)，公司將堅(jiān)持客戶導(dǎo)向、應(yīng)用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長，共同發(fā)展。

問題描述：

實(shí)現(xiàn)代碼與解析：

遞歸（后序）：

原理思路：

迭代（先序）：

原理思路：

問題描述：

給定二叉樹的根節(jié)點(diǎn)?root，返回所有左葉子之和。

示例 1：

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

示例?2:

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

實(shí)現(xiàn)代碼與解析：遞歸（后序）：

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;//記錄左葉子結(jié)點(diǎn)的值
        int rightValue=sumOfLeftLeaves(root->right);
        return leftValue+rightValue;
    }
};

其實(shí)就是把判斷左子樹為左葉子結(jié)點(diǎn)的步驟放在了中序上了而已，因?yàn)樵谥行蚺袛嘧笞訕錇樽笕~子結(jié)點(diǎn)的話，說明從左子樹返回的值一定為0，那么我們直接在父結(jié)點(diǎn)給leftValue賦值即可，減少了一個變量而已，沒什么區(qū)別。返回上一層的操作都還是在后序位置上。

精簡版：

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);
    }
};

原理思路：

? 我們先要明白左葉子結(jié)點(diǎn)是什么？并不是左側(cè)的結(jié)點(diǎn)，而是作為左孩子的葉子結(jié)點(diǎn)，如下圖：

? 因?yàn)槲覀円鸭氖亲笕~子結(jié)點(diǎn)，在遍歷到所指向結(jié)點(diǎn)時，只能判斷該結(jié)點(diǎn)是否為葉子結(jié)點(diǎn)，而不能判斷是左葉子結(jié)點(diǎn)還是右葉子結(jié)點(diǎn)，所以我們要在父結(jié)點(diǎn)的時候就開始判斷左子樹是否為左葉子結(jié)點(diǎn)，大家可以跟著代碼模擬著走一遍，題不難，但是有點(diǎn)繞。

迭代（先序）：

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;
    }
};

原理思路：

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

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

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

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

分享名稱：Leetcode：404.左葉子之和（C++）-創(chuàng)新互聯(lián)
轉(zhuǎn)載源于：http://muchs.cn/article40/ddcoeo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站制作、Google、商城網(wǎng)站、電子商務(wù)、定制網(wǎng)站、網(wǎng)站維護(hù)

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

猜你還喜歡下面的內(nèi)容