99. Recover Binary Search Tree

Description

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Constraints

Approach

Examples

Input: [1, 3, null, null, 2]

Output: [3, 1, null, null, 2]

Solutions

// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode() {}
    
    TreeNode(int val) { this.val = val; }
    
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

Follow up

  • A solution using O(n) space is pretty straight forward.

  • Could you devise a constant space solution?

Last updated

Was this helpful?