404. 左葉子之和

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

我的解法：

思路：相當于樹的廣度優先周遊（BFS），使用一個隊列。

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);
        int res=0;
        while(!q.empty()){
            TreeNode* t=q.front();
            q.pop();
            if(t->left){//有左子樹
                q.push(t->left);
                if(!t->left->left&&!t->left->right)//這個左子樹為左葉子
                {
                    res+=t->left->val;
                    q.pop();
                }    
            }             
            if(t->right)//有右子樹
                q.push(t->right);
        }
        return res;
    }
};
           

問題：runtime error: member access within null pointer of type ‘TreeNode’ (solution.cpp)

發現問題：t有可能為空指針。

改進1.0：

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);
        int res=0;
        while(!q.empty()){
            TreeNode* t=q.front();
            q.pop();
            if(!t)//t為null
                continue;
            if(t->left){//有左子樹
                q.push(t->left);
                if(!t->left->left&&!t->left->right)//這個左子樹為左葉子
                    res+=t->left->val;
            }             
            if(t->right)//有右子樹
                q.push(t->right);
        }
        return res;
    }
};
           

思路：使用一個隊列，所有元素依次入隊，出隊時，驗證符合條件的加和。

資料結構：隊列

時間複雜度：O(n) 空間複雜度：O(n)

總結：第一次完全獨立解決了問題，小有成就感。I just solved on LeetCode. My cpp solution finished in 4 ms, beating 89.39% of all other cpp submissions.

思路2.0 樹的DFS

class Solution {
public:
    //是否為葉子結點
    bool isLeadNode(TreeNode* node){
        return !node->left&&!node->right;
    }
    //深度優先周遊
    int dfs(TreeNode* node){
        int ans=0;
        //有左子樹
        if(node->left){
            //判斷左子樹是否為葉子結點，是加和，否深度周遊
            ans+=isLeadNode(node->left)?node->left->val:dfs(node->left);
        }
        //有右子樹
        if(node->right){
            //直接繼續周遊
            ans+=dfs(node->right);
        }
        return ans;
    }
    int sumOfLeftLeaves(TreeNode* root) {
        return root?dfs(root):0;
    }
};
           

時間複雜度：O(n) 空間複雜度：O(n)。

dfs使用了遞歸。