404

這題從直觀上想起來，會覺得只要把所有的node走過一次，判斷這個node如果是left leaf node，就把這個node的val加上去。概念上寫起來就是:

for all node in tree
{
    if(isLeaf(node->left))
        ans += node->left->val;
}

isLeaf的判斷也很單純，因為我們只會把left child傳進去，所以只要判斷這個node有沒有child就好。

bool isLeaf(TreeNode* node)
{
    if(node == null) 
        return false;

    if(node->left == null && node->right == null)
        return true;
}

剩下唯一的問題就是，該怎麼走過全部的node? 目前手上最簡單的工具就是level order traversal，不過這個演算法不算是很有效率。這邊想到一個直觀的做法，其實只要依序先呼叫root，然後再一直看left跟right child，就可以把所有node都看過一次，這樣子的演算法只會把每個node都走一次，不用先把每一層的node先找出來，再走過這些node，根據這個想法，可以先寫出traverse這個函式，然後在看到每個node的時候再呼叫isLeaf判斷這個node的left child是不是leaf node。寫成程式碼就是:

class Solution {
public:
    int ans = 0;

    int sumOfLeftLeaves(TreeNode* root) {
        traverse(root);
        return ans;
    }

    void traverse(TreeNode* node)
    {
        if(node == NULL)
            return ;
        if(isLeaf(node->left))
            ans += node->left->val;
        traverse(node->left);
        traverse(node->right);
    }

    bool isLeaf(TreeNode* node)
    {
        if(node == NULL)
            return false;
        if(node->left == NULL && node->right == NULL)
            return true;
        return false;
    }
};