1. 题目描述

计算给定二叉树的所有左叶子之和。示例：

  1. 3
  2.    / \
  3.   9  20
  4.     /  \
  5.    15   7

在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

2. 解题思路

对于这道题目，我们可以对二叉树进行层序遍历，初始化一个对来queue来保存当前层的元素，遍历队列中的元素，如果该节点的左子树不存在左右子树，说明它是一个左叶子节点，将其加在结果上。

复杂度分析：

  • 时间复杂度：O(n)，最坏的情况下，也就是二叉树只有右子树，而形成一个链表的时候，我们需要遍历完整个二叉树，时间复杂度就是 O(n)；

  • 空间复杂度：O(n)，其中n表示队列的长度，这个长度永远小于等于二叉树的节点的数量。

    3. 代码实现

    1. /**
    2. * Definition for a binary tree node.
    3. * function TreeNode(val) {
    4. *     this.val = val;
    5. *     this.left = this.right = null;
    6. * }
    7. */
    8. /**
    9. * @param {TreeNode} root
    10. * @return {number}
    11. */
    12. var sumOfLeftLeaves = function(root) {
    13.   if(!root) return 0
    14.   let res = 0
    15.   const queue = [root]
    17.   while(queue.length){
    18.       const cur = queue.shift()
    19.       if(cur.left){
    20.           if(!cur.left.left && !cur.left.right){
    21.               res += cur.left.val
    22.           }
    23.           queue.push(cur.left)
    24.       }
    25.       if(cur.right){
    26.           queue.push(cur.right)
    27.       }
    28.   }
    29.   return res
    30. };

    4. 提交结果

    image.png