题目
计算给定二叉树的所有左叶子之和。
示例:
3 / \ 9 20 / \ 15 7 在这个二叉树中,有两个左叶子,分别是 9 和 15,所以返回 24
解题
方法一:BFS
python解法
注意题目中写的是 左叶子节点,不是左子节点.
# 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 = right class Solution: def sumOfLeftLeaves(self, root: TreeNode) -> int: if not root: return 0 queue = [root] num = 0 while queue: l = len(queue) for i in range(l): cur = queue.pop(0) left,right = cur.left,cur.right if left:# 判断左子节点 queue.append(left) if not (left.left or left.right):# 判断叶子节点 num+=left.val if right: queue.append(right) return num
c++解法
由于只有根节点的情况是不算的左叶子节点的,所以不能考虑根节点,直接在if left 里面判断是否为叶子节点就行了
class Solution { public: int sumOfLeftLeaves(TreeNode* root) { if(!root) return 0; queue<TreeNode*> queue; queue.push(root); int res=0; while(!queue.empty()){ TreeNode* cur=queue.front(); queue.pop(); if(cur->left){ queue.push(cur->left); if(!(cur->left->left||cur->left->right)){ res+=cur->left->val; } } if(cur->right){ queue.push(cur->right); } } return res; } };
java写法
class Solution { public int sumOfLeftLeaves(TreeNode root) { if(root==null) return 0; Queue<TreeNode> q=new LinkedList<>(); q.add(root); int res=0; while(!q.isEmpty()){ TreeNode cur=q.poll(); if(cur.left!=null){ if(cur.left.left==null&&cur.left.right==null){ res+=cur.left.val; } q.add(cur.left); } if(cur.right!=null){ q.add(cur.right); } } return res; } }