Leetcode

Sum of Left Leaves

Approach 1: Recursive

  • Time:O(n)
  • Space:O(h)

C++

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;
  }
};

JAVA

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)

C++

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;
  }
};

JAVA

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;
  }
}