临沂做商城网站网站建设官方网站

题目链接

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 0ans = 0if root.left != None and root.left.left == None and root.left.right == None:ans = ans + root.left.valans = ans + self.sumOfLeftLeaves(root.left) + self.sumOfLeftLeaves(root.right)return ans