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)
      return 0;

    int ans = 0;

    if (root->left) {
      if (!root->left->left && !root->left->right)
        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;
  }
}

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)
      return 0;

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

    while (!stack.empty()) {
      root = stack.top(), stack.pop();
      if (root->left) {
        if (!root->left->left && !root->left->right)
          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;
  }
}