Leetcode.404 左叶子之和

题目链接

Leetcode.404 左叶子之和 easy

题目描述

给定二叉树的根节点 root，返回所有 左叶子 之和。

示例 1：

输入: root = [3,9,20,null,null,15,7]
输出: 24
解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

示例 2：

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

提示：

• 节点数在 $[1,1000]$ 范围内
• $-1000<=Node.val<=1000$

解法：递归

判断当前结点 root的左子结点 root.left是否为 左叶子结点 ，如果是，答案 ans就加上 左叶子结点的值 root.left.val。

时间复杂度：$O(n)$

C++代码：

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if(root == nullptr) return 0;
        int ans = 0;
        if(root->left && root->left->left == nullptr && root->left->right == nullptr){
            ans += root->left->val;
        }

        ans += sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);

        return ans;
    }
};

Python代码：

class Solution:
    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
        if root == None:
            return 0
        ans = 0
        if root.left != None and root.left.left == None and root.left.right == None:
            ans = ans + root.left.val

        ans = ans + self.sumOfLeftLeaves(root.left) + self.sumOfLeftLeaves(root.right)
        return ans