99. Recover Binary Search Tree

Problem

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

Recover the tree without changing its structure.

Example 1:

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

   1
  /
 3
  \
   2

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

   3
  /
 1
  \
   2

Example 2:

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

  3
 / \
1   4
   /
  2

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

  2
 / \
1   4
   /
  3

Follow up:

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

Solution 1

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var recoverTree = function(root) {
  var data = {
    prev: null,
    first: null,
    second: null
  };
  var tmp = 0;

  helper(root, data);

  tmp = data.first.val;
  data.first.val = data.second.val;
  data.second.val = tmp;
};

var helper = function (root, data) {
  if (!root) return;

  helper(root.left, data);

  if (data.prev && data.prev.val >= root.val) {
    if (!data.first) data.first = data.prev;
    data.second = root;
  }

  data.prev = root;

  helper(root.right, data);
};

Explain:

nope.

Complexity:

• Time complexity : O(n). n 为节点数。
• Space complexity : O(1).

Solution 2

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var recoverTree = function(root) {
  var prev = null;
  var first = null;
  var second = null;
  var now = root;
  var stack = [];
  var tmp = 0;

  while (now || stack.length) {
    while (now) {
      stack.push(now);
      now = now.left;
    }

    now = stack.pop();

    if (prev && prev.val >= now.val) {
      if (!first) first = prev;
      second = now;
    }

    prev = now;
    now = now.right;
  }

  tmp = first.val;
  first.val = second.val;
  second.val = tmp;
};

Explain:

nope.

Complexity:

• Time complexity : O(n). n 为节点数。
• Space complexity : O(n).