Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/99.html

99	Recover Binary Search Tree

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

Recover the tree without changing its structure.

Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

@tag-tree

Algorithm

Three pointers are needed, first and second respectively represent the first and second disordered nodes, and pre points to the previous node of the current node’s in-order traversal.

The traditional in-order traversal recursion is used here, but where the node value should be output, it is replaced by judging the size of pre and the current node value. If pre is larger, if first is empty, first point to the node pointed to by pre, or else, set second to the current node.

In this way, the in-order traverses the entire tree, and if both first and second exist, then their node values can be exchanged. The space complexity of this algorithm is still O(n), where n is the height of the tree.

Code

Java

  • 
    public class Recover_Binary_Search_Tree {
    
        public static void main(String[] args) {
    
        }
    
        /**
         * Definition for a binary tree node.
         * public class TreeNode {
         * int val;
         * TreeNode left;
         * TreeNode right;
         * TreeNode(int x) { val = x; }
         * }
         */
    
        public class Solution {
    
            TreeNode n1;
            TreeNode n2;
            TreeNode prev; // @note:@memorize: key is use prev!
    
            public void recoverTree(TreeNode root) {
                inOrderTraversal(root); // will record 2 swapped nodes
                swap(); // swap 2 nodes
            }
    
            private void inOrderTraversal(TreeNode root) {
    
                if (root == null) {
                    return;
                }
    
                inOrderTraversal(root.left);
    
    
                // @note: 1,6,3,4,5,2 => NOT next to each other => n1=6-prev, but n2=2-root
                // @note: 1,2,4,3,5,6 => when next to each other, n2 needs to be root
                // bigger than next, then wrong
    
                if (prev != null && prev.val >= root.val) {
                    if (n1 == null) {
                        n1 = prev;
                        n2 = root; // @note:@memorize: here is key, for case when in total two nodes
                    } else {
                        // n2 = prev; @note:@memorize: n1 and n2, n1=prev but n2=root
                        n2 = root;
                    }
                }
    
                prev = root;
    
                inOrderTraversal(root.right);
            }
    
            // @note: concern about n1 or n2 is null? by question definition, if swapped, then at least 2 nodes
            private void swap() {
                int tmp = n1.val;
                n1.val = n2.val;
                n2.val = tmp;
            }
        }
    
    }
    
    
  • // OJ: https://leetcode.com/problems/recover-binary-search-tree/
    // Time: O(N)
    // Space: O(H)
    class Solution {
        TreeNode *a = NULL, *b = NULL;
        void update(TreeNode *x, TreeNode *y) {
            if (!a || x->val < a->val) a = x;
            if (!b || y->val > b->val) b = y;
        }
        void dfs(TreeNode *root, TreeNode *left = NULL, TreeNode *right = NULL) {
            if (!root) return;
            if (left && left->val > root->val) update(root, left);
            if (right && right->val < root->val) update(right, root);
            dfs(root->left, left, root);
            dfs(root->right, root, right);
        }
    public:
        void recoverTree(TreeNode* root) {
            dfs(root);
            swap(a->val, b->val);
        }
    };
    
  • # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, val=0, left=None, right=None):
    #         self.val = val
    #         self.left = left
    #         self.right = right
    class Solution:
        def recoverTree(self, root: Optional[TreeNode]) -> None:
            """
            Do not return anything, modify root in-place instead.
            """
    
            def dfs(root):
                if root is None:
                    return
                nonlocal prev, first, second
                dfs(root.left)
                if prev and prev.val > root.val:
                    if first is None:
                        first = prev
                    second = root
                prev = root
                dfs(root.right)
    
            prev = first = second = None
            dfs(root)
            first.val, second.val = second.val, first.val
    
    ############
    
    class Solution:
      def __init__(self):
        self.n1 = None
        self.n2 = None
        self.pre = None
    
      def findBadNode(self, root):
        if root is None: return
        self.findBadNode(root.left)
        if self.pre is not None:
          if root.val < self.pre.val:
            if self.n1 is None:
              self.n1 = self.pre
              self.n2 = root
            else:
              self.n2 = root
        self.pre = root
        self.findBadNode(root.right)
    
      def recoverTree(self, root):
        self.findBadNode(root)
        if self.n1 is not None and self.n2 is not None:
          self.n1.val, self.n2.val = self.n2.val, self.n1.val
    
    

All Problems

All Solutions