TNotes.leetcode

Appearance

0404. 左叶子之和【简单】

0404. 左叶子之和【简单】 ​

1. 📝 题目描述 ​

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

示例 1：

img

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

示例 2：

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

提示：

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

2. 🎯 s.1 - 递归 ​

js
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumOfLeftLeaves = function (root) {
  if (!root) return 0

  // 判断是否为左叶子节点的函数
  const isLeaf = (node) => {
    return node && !node.left && !node.right
  }

  let sum = 0

  // 如果左子节点是叶子节点
  if (isLeaf(root.left)) {
    sum += root.left.val
  }

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

  return sum
}
  • 时间复杂度：O(n)，其中 n 是二叉树的节点数，需要遍历每个节点
  • 空间复杂度：O(h)，其中 h 是二叉树的高度，递归调用栈的深度
  • 算法思路：
    • 可以通过深度优先搜索(DFS)遍历二叉树，在遍历过程中判断每个节点是否为左叶子节点
    1. 遍历二叉树的每个节点
    2. 对于每个节点，检查它的左子节点是否为叶子节点
    3. 如果是左叶子节点，则将其值加到结果中
    4. 递归处理左右子树

Discussions