题目描述：

恢复二叉搜索树 - 图1

代码实现：

  • 还不是很懂
  • 时间复杂度：O(n)
  1. /**
  2.  * Definition for a binary tree node.
  3.  * function TreeNode(val) {
  4.  *     this.val = val;
  5.  *     this.left = this.right = null;
  6.  * }
  7.  */
  8. /**
  9.  * @param {TreeNode} root
  10.  * @return {void} Do not return anything, modify root in-place instead.
  11.  */
  12. var recoverTree = function(root) {
  13.     if (!root) {
  14.         return null
  15.     }
  16.     var curr = root
  17.     var node1 = null
  18.     var node2 = null
  19.     var lastNode = null
  20.     while (curr) {
  21.         if (curr.left) {
  22.             var preNode = curr.left
  23.             while (preNode.right && preNode.right != curr) {
  24.                 preNode = preNode.right
  25.             }
  26.             if (!preNode.right) {
  27.                 preNode.right = curr
  28.                 curr = curr.left
  29.             } else { 
  30.                 if (lastNode && lastNode.val > curr.val) {
  31.                     if (node1) {
  32.                         node2 = curr
  33.                     } else {
  34.                         node1 = lastNode
  35.                         node2 = curr
  36.                     }  
  37.                 }
  39.                 lastNode = curr
  40.                 curr = curr.right
  41.                 preNode.right = null
  42.             }
  43.         } else {
  44.             if (lastNode && lastNode.val > curr.val) {
  45.                 if (node1) {
  46.                     node2 = curr
  47.                 } else {
  48.                     node1 = lastNode
  49.                     node2 = curr
  50.                 }
  51.             }
  53.             lastNode = curr
  54.             curr = curr.right
  55.         }
  57.     }
  58.     const tmp = node1.val
  59.     node1.val = node2.val
  60.     node2.val = tmp
  61. };

恢复二叉搜索树 - 图2