06、左叶子之和

哈喽，大家好，我是厨子，今天给大家写一下左叶子之和这个题目

https://leetcode.cn/problems/sum-of-left-leaves/?envType=problem-list-v2&envId=binary-tree

题目描述

给定二叉树的根节点 root，返回所有左叶子之和。

示例 1:

输入: root = [3,9,20,null,null,15,7]
输出: 24
解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
        3
       / \
      9  20
        /  \
       15   7

左叶子: 9, 15
和: 9 + 15 = 24

示例 2:

输入: root = [1]
输出: 0

约束条件:

• 节点数在 [1, 1000] 范围内
• -1000 <= Node.val <= 1000

什么是左叶子？

左叶子的定义

左叶子必须同时满足两个条件：

1. 是某个节点的左子节点
2. 本身是叶子节点（没有左右子节点） 1.

        3
       / \
      9  20
        /  \
       15   7

节点9:  是3的左子节点 ✓, 是叶子节点 ✓  → 左叶子 ✓
节点20: 是3的右子节点 ✗               → 不是左叶子
节点15: 是20的左子节点 ✓, 是叶子节点 ✓  → 左叶子 ✓
节点7:  是20的右子节点 ✗              → 不是左叶子

解题思路

遍历二叉树，对于每个节点：

1. 检查它的左子节点是否是叶子
2. 如果是，加上左子节点的值
3. 递归处理左右子树

判断左叶子的条件

// 节点 node 的左子节点是左叶子的条件：
node->left != nullptr &&           // 左子节点存在
node->left->left == nullptr &&     // 左子节点没有左孩子
node->left->right == nullptr       // 左子节点没有右孩子

算法流程

暂时无法在飞书文档外展示此内容

图解示例

以示例1为例：[3,9,20,null,null,15,7]

        3
       / \
      9  20
        /  \
       15   7

步骤1: 访问节点3
  ├─ 检查左子节点9
  │  └─ 9是叶子 ✓ → sum += 9
  ├─ 递归左子树: sumOfLeftLeaves(9)
  │  └─ 9没有子节点，返回 0
  └─ 递归右子树: sumOfLeftLeaves(20)
      ├─ 检查左子节点15
      │  └─ 15是叶子 ✓ → sum += 15
      ├─ 递归左子树: sumOfLeftLeaves(15)
      │  └─ 15没有子节点，返回 0
      └─ 递归右子树: sumOfLeftLeaves(7)
          └─ 7没有子节点，返回 0

结果: 9 + 15 = 24

大家在完成这个题目的过程中，最难的是不懂如何递归，这块也没有特别好的办法，需要多加练习和总结

代码实现

递归

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }

        int sum = 0;

        // 检查左子节点是否是左叶子，上面提到的三个内容
        if (root->left != nullptr &&
            root->left->left == nullptr &&
            root->left->right == nullptr) {
            sum += root->left->val;
        }

        // 递归处理左右子树
        sum += sumOfLeftLeaves(root->left);
        sum += sumOfLeftLeaves(root->right);

        return sum;
    }
};

时间复杂度: O(n)，n 是节点总数，每个节点访问一次

空间复杂度: O(h)，h 是树的高度（递归栈深度）

迭代

使用队列进行层序遍历。

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }

        queue<TreeNode*> q;
        q.push(root);
        int sum = 0;

        while (!q.empty()) {
            TreeNode* node = q.front();
            q.pop();

            // 检查左子节点是否是左叶子
            if (node->left != nullptr) {
                if (node->left->left == nullptr &&
                    node->left->right == nullptr) {
                    sum += node->left->val;
                } else {
                    q.push(node->left);
                }
            }

            // 右子节点不是左叶子，但需要继续遍历
            if (node->right != nullptr) {
                q.push(node->right);
            }
        }

        return sum;
    }
};

时间复杂度: O(n)

空间复杂度: O(w)，w 是树的最大宽度

迭代（DFS + 栈）

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }

        stack<TreeNode*> st;
        st.push(root);
        int sum = 0;

        while (!st.empty()) {
            TreeNode* node = st.top();
            st.pop();

            // 检查左子节点是否是左叶子
            if (node->left != nullptr &&
                node->left->left == nullptr &&
                node->left->right == nullptr) {
                sum += node->left->val;
            }

            // 继续遍历左右子树
            if (node->left != nullptr) {
                st.push(node->left);
            }
            if (node->right != nullptr) {
                st.push(node->right);
            }
        }

        return sum;
    }
};

时间复杂度: O(n)

空间复杂度: O(h)