Given the root of a binary tree, return the sum of all left leaves.
A leaf is a node with no children. A left leaf is a leaf that is the left child of another node.
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: 24
Explanation: There are two left leaves in the binary tree, with values 9 and 15 respectively.
Example 2:
Input: root = [1]
Output: 0
Constraints:
The number of nodes in the tree is in the range [1, 1000].
-1000 <= Node.val <= 1000
Solutions
Solution 1: Recursion
First, we check if root is null. If it is, we return $0$.
Otherwise, we recursively call the sumOfLeftLeaves function to calculate the sum of all left leaves in root's right subtree, and assign the result to the answer variable $ans$. Then we check if root's left child exists. If it does, we check if it is a leaf node. If it is a leaf node, we add its value to the answer variable $ans$. Otherwise, we recursively call the sumOfLeftLeaves function to calculate the sum of all left leaves in root's left subtree, and add the result to the answer variable $ans$.
Finally, we return the answer.
The time complexity is $O(n)$, and the space complexity is $O(n)$, where $n$ is the number of nodes in the binary tree.
1 2 3 4 5 6 7 8 91011121314151617
# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclassSolution:defsumOfLeftLeaves(self,root:Optional[TreeNode])->int:ifrootisNone:return0ans=self.sumOfLeftLeaves(root.right)ifroot.left:ifroot.left.left==root.left.right:ans+=root.left.valelse:ans+=self.sumOfLeftLeaves(root.left)returnans
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcsumOfLeftLeaves(root*TreeNode)int{ifroot==nil{return0}ans:=sumOfLeftLeaves(root.Right)ifroot.Left!=nil{ifroot.Left.Left==root.Left.Right{ans+=root.Left.Val}else{ans+=sumOfLeftLeaves(root.Left)}}returnans}
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */intsumOfLeftLeaves(structTreeNode*root){if(!root){return0;}intans=sumOfLeftLeaves(root->right);if(root->left){if(!root->left->left&&!root->left->right){ans+=root->left->val;}else{ans+=sumOfLeftLeaves(root->left);}}returnans;}
Solution 2: Stack
We can also convert the recursion in Solution 1 to iteration, using a stack to simulate the recursion process.
Similar to Solution 1, we first check if root is null. If it is, we return $0$.
Otherwise, we initialize the answer variable $ans$ to $0$, and then initialize a stack $stk$ and add root to the stack.
While the stack is not empty, we pop the top element root from the stack. If root's left child exists, we check if it is a leaf node. If it is a leaf node, we add its value to the answer variable $ans$. Otherwise, we add its left child to the stack. Then we check if root's right child exists. If it does, we add it to the stack.
Finally, we return the answer.
The time complexity is $O(n)$, and the space complexity is $O(n)$, where $n$ is the number of nodes in the binary tree.
1 2 3 4 5 6 7 8 910111213141516171819202122
# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclassSolution:defsumOfLeftLeaves(self,root:Optional[TreeNode])->int:ifrootisNone:return0ans=0stk=[root]whilestk:root=stk.pop()ifroot.left:ifroot.left.left==root.left.right:ans+=root.left.valelse:stk.append(root.left)ifroot.right:stk.append(root.right)returnans
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcsumOfLeftLeaves(root*TreeNode)(ansint){ifroot==nil{return0}stk:=[]*TreeNode{root}forlen(stk)>0{root=stk[len(stk)-1]stk=stk[:len(stk)-1]ifroot.Left!=nil{ifroot.Left.Left==root.Left.Right{ans+=root.Left.Val}else{stk=append(stk,root.Left)}}ifroot.Right!=nil{stk=append(stk,root.Right)}}return}