难度简单564收藏分享切换为英文接收动态反馈
给定二叉树的根节点 root ，返回所有左叶子之和。
示例 1：
输入: root = [3,9,20,null,null,15,7]
输出: 24
解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24示例 2:
输入: root = [1]
输出: 0提示:
- 节点数在
[1, 1000]范围内 -1000 <= Node.val <= 1000
1、递归法
递归法这里举两个不同的写法，第一个我觉得我会比较好理解，而第二个总的来说代码会更加简洁！
其实两种写法是类似的，只不过第一种写法我们需要一个子函数，其中参数有两个，一个是 parent 结点，一个是 cur 结点，因为我们要去求一棵树的左叶子，那么我们可以判断当前这个 cur 是否是叶子节点，加上如果 parent->left 就是 cur 的话，则说明当前就是左叶子结点；如果不是的话，则将 parent 变成 cur，让 cur 继续递归到其左右子树进行查找！
class Solution {
public:
int sum(TreeNode* parent, TreeNode* cur)
{
if(cur == nullptr)
return 0;
// 如果当前是叶子节点且为父亲节点的左孩子，那么就是左叶子结点！
if(cur->left == nullptr && cur->right == nullptr && parent->left == cur)
{
return cur->val;
}
// 如果不是的话，则将parent变成cur，让cur继续递归到其左右子树进行查找
parent = cur;
return sum(parent, cur->left) + sum(parent, cur->right);
}
int sumOfLeftLeaves(TreeNode* root) {
// 通过子函数递归
return sum(root, root->left) + sum(root, root->right);
}
}; 第二种写法就是我们只需要一个参数，然后思路和第一种写法还是一样的，我们只需要判断当前 cur 的左孩子不为空并且这个左孩子就是叶子节点的话，那么就是我们要求的左叶子结点，但是不同的是我们不能直接 return root->val，因为我们的 root 可能还有右子树，它这个右子树可能还存在左叶子结点，所以我们需要将这个值记录下来并且继续递归 root 的左子树和右子树去寻找其它的左叶子结点！
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
if(root == nullptr)
return 0;
int sum = 0;
// 如果cur存在左孩子且为叶子节点，那么就是左叶子结点！
if(root->left != nullptr && root->left->left == nullptr && root->left->right == nullptr)
sum = root->left->val;
return sum + sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
}
};2、迭代法
迭代法这里采用的是层序遍历！
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
queue<TreeNode*> qe;
qe.push(root);
int sum = 0;
while(!qe.empty())
{
TreeNode* cur = qe.front();
qe.pop();
// 如果cur存在左孩子且为叶子节点，那么就是左叶子结点！
if(cur->left != nullptr && cur->left->left == nullptr && cur->left->right == nullptr)
sum += cur->left->val;
if(cur->left)
qe.push(cur->left);
if(cur->right)
qe.push(cur->right);
}
return sum;
}
};