[C++]LeetCode404. 左叶子之和

[C++]LeetCode404. 左叶子之和

404. 左叶子之和

当遇到左叶子节点的时候，记录数值，然后通过递归求取左子树左叶子之和，和 右子树左叶子之和，相加便是整个树的左叶子之和。
深度优先搜索

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if(root == NULL) return 0;
        //递归求左子树的左叶子节点
        int leaftvalue = sumOfLeftLeaves(root->left);
        //递归求右子树的左叶子节点
        int rightvalue = sumOfLeftLeaves(root->right);
        int midvalue = 0;
        //左叶子节点不为空，且左叶子节点的左右子节点为空，则记录当前左叶子节点的值
        if(root->left && !root->left->left && !root->left->right)
        {
            midvalue = root->left->val;
        }
        //最终累加求和
        int sum = midvalue + leaftvalue + rightvalue;
        return sum;
    }
};
class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        return root ? dfs(root) : 0;
    }
    int dfs(TreeNode* root)
    {
        int ans = 0;
        if(root->left)
            ans += isLeaves(root->left) ? root->left->val : dfs(root->left);
        if(root->right && !isLeaves(root->right))
            ans += dfs(root->right);
        return ans;
    }
    bool isLeaves(TreeNode* root)
    {
        return root->left == NULL && root->right == NULL;
    }
};

时间复杂度：O(n)，其中 n是树中的节点个数。
空间复杂度：O(n)。空间复杂度与深度优先搜索使用的栈的最大深度相关。在最坏的情况下，树呈现链式结构，深度为 O(n)，对应的空间复杂度也为 O(n)。