Leetcode-404：左叶子之和

404. 左叶子之和
题目描述：
给定二叉树的根节点 root ，返回所有左叶子之和。

深度优先（O(N),O(N)）

class Solution {
    
public:
    void  getLeftNum(TreeNode* root, int &n){
    
        // 根节点为空或者只有一个节点则返回
        if(!root->left && !root->right || root == nullptr )  return;
        // 该节点有左叶子就加和
        else if(root->left != nullptr && root->left->left == nullptr && root->left->right==nullptr) n+=root->left->val;
        //否则继续处理左子树
        else if(root->left)
            getLeftNum(root->left,n);
        // 处理右子树 
        if(root->right)
            getLeftNum(root->right,n);
    }
    int sumOfLeftLeaves(TreeNode* root) {
    
        int n =0 ;
        getLeftNum(root,n);
        return n;
    }
};

广度优先（O(N),O(N)）

class Solution {
    
public:
    int sumOfLeftLeaves(TreeNode* root) {
    
        if(!root->left && !root->right || root==nullptr) return 0;
        // 初始化返回值
        int res=0;
        // 广度优先遍历
        queue<TreeNode*> que;
        que.push(root);
        // 广度优先遍历处理模板
        while(!que.empty()){
    
            TreeNode* node = que.front();
            que.pop();
            // 左孩子入队
            if(node->left){
    
                que.push(node->left) ;
                // 如果左孩子是叶子节点就加和
                if(node->left->left == nullptr && node->left->right == nullptr)
                res+=node->left->val;
            }  
            // 右孩子入队
            if(node->right) que.push(node->right);
        }
        return res;    
    }
};