Skip to content

404. Sum of Left Leaves 👍

Approach 1: Recursive

  • Time: $O(n)$
  • Space: $O(h)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
 public:
  int sumOfLeftLeaves(TreeNode* root) {
    if (root == nullptr)
      return 0;

    int ans = 0;

    if (root->left) {
      if (root->left->left == nullptr && root->left->right == nullptr)
        ans += root->left->val;
      else
        ans += sumOfLeftLeaves(root->left);
    }
    ans += sumOfLeftLeaves(root->right);

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
  public int sumOfLeftLeaves(TreeNode root) {
    if (root == null)
      return 0;

    int ans = 0;

    if (root.left != null) {
      if (root.left.left == null && root.left.right == null)
        ans += root.left.val;
      else
        ans += sumOfLeftLeaves(root.left);
    }
    ans += sumOfLeftLeaves(root.right);

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
  def sumOfLeftLeaves(self, root: TreeNode | None) -> int:
    if not root:
      return 0

    ans = 0

    if root.left:
      if not root.left.left and not root.left.right:
        ans += root.left.val
      else:
        ans += self.sumOfLeftLeaves(root.left)
    ans += self.sumOfLeftLeaves(root.right)

    return ans

Approach 2: Iterative

  • Time: $O(n)$
  • Space: $O(h)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
 public:
  int sumOfLeftLeaves(TreeNode* root) {
    if (root == nullptr)
      return 0;

    int ans = 0;
    stack<TreeNode*> stack{{root}};

    while (!stack.empty()) {
      root = stack.top(), stack.pop();
      if (root->left) {
        if (root->left->left == nullptr && root->left->right == nullptr)
          ans += root->left->val;
        else
          stack.push(root->left);
      }
      if (root->right)
        stack.push(root->right);
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
  public int sumOfLeftLeaves(TreeNode root) {
    if (root == null)
      return 0;

    int ans = 0;
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);

    while (!stack.isEmpty()) {
      root = stack.pop();
      if (root.left != null) {
        if (root.left.left == null && root.left.right == null)
          ans += root.left.val;
        else
          stack.push(root.left);
      }
      if (root.right != null)
        stack.push(root.right);
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
  def sumOfLeftLeaves(self, root: TreeNode | None) -> int:
    if not root:
      return 0

    ans = 0
    stack = [root]

    while stack:
      root = stack.pop()
      if root.left:
        if not root.left.left and not root.left.right:
          ans += root.left.val
        else:
          stack.append(root.left)
      if root.right:
        stack.append(root.right)

    return ans