Leetcode.404 左叶子之和
题目链接
题目描述
给定二叉树的根节点 root
,返回所有 左叶子 之和。
示例 1:
输入: root = [3,9,20,null,null,15,7]
输出: 24
解释: 在这个二叉树中,有两个左叶子,分别是 9 和 15,所以返回 24
示例 2:
输入: root = [1]
输出: 0
提示:
- 节点数在 [1,1000][1, 1000][1,1000] 范围内
- −1000<=Node.val<=1000-1000 <= Node.val <= 1000−1000<=Node.val<=1000
解法:递归
判断当前结点 root
的左子结点 root.left
是否为 左叶子结点 ,如果是,答案 ans
就加上 左叶子结点的值 root.left.val
。
时间复杂度:O(n)O(n)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