Skip to content

1660. Correct a Binary Tree 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
 public:
  TreeNode* correctBinaryTree(TreeNode* root) {
    if (root == nullptr)
      return nullptr;
    if (root->right != nullptr && seen.contains(root->right->val))
      return nullptr;
    seen.insert(root->val);
    root->right = correctBinaryTree(root->right);
    root->left = correctBinaryTree(root->left);
    return root;
  }

 private:
  unordered_set<int> seen;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
  public TreeNode correctBinaryTree(TreeNode root) {
    if (root == null)
      return null;
    if (root.right != null && seen.contains(root.right.val))
      return null;
    seen.add(root.val);
    root.right = correctBinaryTree(root.right);
    root.left = correctBinaryTree(root.left);
    return root;
  }

  private Set<Integer> seen = new HashSet<>();
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
  def __init__(self):
    self.seen = set()

  def correctBinaryTree(self, root: TreeNode | None) -> TreeNode | None:
    if root == None:
      return None
    if root.right and root.right.val in self.seen:
      return None
    self.seen.add(root.val)
    root.right = self.correctBinaryTree(root.right)
    root.left = self.correctBinaryTree(root.left)
    return root