Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

1080. Insufficient Nodes in Root to Leaf Paths

Time: $O(n)$

Space: $O(h)$

			


class Solution {
 public:
  TreeNode* sufficientSubset(TreeNode* root, int limit) {
    if (root == nullptr)
      return nullptr;
    if (root->left == nullptr && root->right == nullptr)
      return root->val < limit ? nullptr : root;

    root->left = sufficientSubset(root->left, limit - root->val);
    root->right = sufficientSubset(root->right, limit - root->val);

    // Both children are nullptr
    return root->left == root->right ? nullptr : root;
  }
};




			


class Solution {
  public TreeNode sufficientSubset(TreeNode root, int limit) {
    if (root == null)
      return null;
    if (root.left == null && root.right == null)
      return root.val < limit ? null : root;

    root.left = sufficientSubset(root.left, limit - root.val);
    root.right = sufficientSubset(root.right, limit - root.val);

    // Both children are null
    return root.left == root.right ? null : root;
  }
}