100 - 左叶子之和

题目

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

示例：

​ 3

/ 9 20 / 15 7

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

解答

感觉是一个深度优先的遍历

迭代

作者：pandawakaka 链接：https://leetcode-cn.com/problems/sum-of-left-leaves/solution/zuo-zi-xie-zhi-he-python3di-gui-by-pandawakaka/

var sumOfLeftLeaves = function (root) {
  if (root === null) {
    return 0
  }
  let stack = [root], res = 0
  while (stack.length > 0) {
    let cur = stack.pop()
    if (cur.left && !cur.left.left && !cur.left.right) {
      res += cur.left.val
    } else if (cur.left) {
      stack.push(cur.left)
    }
    if (cur.right) {
      stack.push(cur.right)
    }
  }
  return res
};

Runtime: 60 ms, faster than 40.68% of JavaScript online submissions for Sum of Left Leaves.

Memory Usage: 34.2 MB, less than 100.00% of JavaScript online submissions for Sum of Left Leaves.

func sumOfLeftLeaves(root *TreeNode) int {
    if root == nil {
        return 0
    }
    stack := []*TreeNode{root}
    var res int
    for len(stack) > 0 {
        cur := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        if cur.Left != nil && cur.Left.Left == nil && cur.Left.Right == nil {
            res += cur.Left.Val
        } else if cur.Left != nil {
            stack = append(stack, cur.Left)
        }
        if cur.Right != nil {
            stack = append(stack, cur.Right)
        }
    }
    return res
}

Runtime: 0 ms, faster than 100.00% of Go online submissions for Sum of Left Leaves.

Memory Usage: 2.6 MB, less than 100.00% of Go online submissions for Sum of Left Leaves.

class Solution:
    def sumOfLeftLeaves(self, root: TreeNode) -> int:
        if not root:
            return 0
        stack = [root]
        res = 0
        while stack:
            cur = stack.pop()
            if cur.left and not cur.left.left and not cur.left.right:
                res += cur.left.val
            elif cur.left:
                stack.append(cur.left)
            if cur.right:
                stack.append(cur.right)
        return res

Runtime: 44 ms, faster than 26.94% of Python3 online submissions for Sum of Left Leaves.

Memory Usage: 13.8 MB, less than 76.92% of Python3 online submissions for Sum of Left Leaves.

python还能直接用list的变量名，来判断这个list是否还有值。。厉害了😂

是不是一旦为空就都指向一个相同的空数组啊？还是自动被gc了？

递归

class Solution:
    def sumOfLeftLeaves(self, root: TreeNode) -> int:
        if not root:
            return 0
        if root and root.left and not root.left.left and not root.left.right:
            return root.left.val + self.sumOfLeftLeaves(root.right)
        return self.sumOfLeftLeaves(root.left) + self.sumOfLeftLeaves(root.right)

Runtime: 44 ms, faster than 26.94% of Python3 online submissions for Sum of Left Leaves.

Memory Usage: 14.3 MB, less than 7.69% of Python3 online submissions for Sum of Left Leaves.

func sumOfLeftLeaves(root *TreeNode) int {
    if root == nil {
        return 0
    }
    if root != nil && root.Left!=nil && root.Left.Left==nil && root.Left.Right==nil {
        return root.Left.Val + sumOfLeftLeaves(root.Right)
    }
    return sumOfLeftLeaves(root.Left)+sumOfLeftLeaves(root.Right)
}

Runtime: 0 ms, faster than 100.00% of Go online submissions for Sum of Left Leaves.

Memory Usage: 2.7 MB, less than 100.00% of Go online submissions for Sum of Left Leaves.

明明多用了0.1MB，为啥还是100%？🤪

var sumOfLeftLeaves = function (root) {
  if (root === null) {
    return 0
  }
  if (root && root.left && !root.left.left && !root.left.right) {
    return root.left.val + sumOfLeftLeaves(root.right)
  }
  return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right)
};

Runtime: 56 ms, faster than 67.12% of JavaScript online submissions for Sum of Left Leaves.

Memory Usage: 34.4 MB, less than 100.00% of JavaScript online submissions for Sum of Left Leaves.