原文：99. 恢复二叉搜索树(leetcode 解题) - 每天一个JavaScript小知识@Js中文网 · 码农进阶题库

原文地址：https://www.javascriptc.com/interview-tips/zh_cn/leetcode/leetcode-javascript-solution-099/

题目：

难度：Hard

相关话题：树、深度优先搜索

二叉搜索树中的两个节点被错误地交换。

请在不改变其结构的情况下，恢复这棵树。

示例1:

输入: [1,3,null,null,2]

  1
 /
3
 \
  2

输出: [3,1,null,null,2]

  3
 /
1
 \
  2

示例2:

输入: [3,1,4,null,null,2]

  3
 / \
1   4
  /
 2

输出: [2,1,4,null,null,3]

  2
 / \
1   4
  /
 3

进阶:

  • 使用 O(n ) 空间复杂度的解法很容易实现。

  • 你能想出一个只使用常数空间的解决方案吗？

思路：

这道题关键就是利用二叉搜索树的中序遍历，找出不符合要求的2个节点。

其中O(n)的思路是，使用一个数组保存中序遍历的结果，然后找出错误排序的2个节点，通过交换即可。

/**
 * @来源： Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍：一个致力于帮助开发者用代码改变世界为使命的平台，每天都可以在这里找到技术世界的头条内容
 * 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) {
  let aux=[]
  function dfs(root){
    if(root.left)dfs(root.left)
    aux.push(root)
    if(root.right)dfs(root.right)
  }
  dfs(root)
  let s1,s2
  for(let i=0;i<aux.length-1;i++){
    if(aux[i].val>aux[i+1].val){
      if(s1==null)s1=aux[i]
      if(s1!=null)s2=aux[i+1]
    }
  }
  let t=s1.val
  s1.val=s2.val
  s2.val=t
};

O(1)的思路也差不多，不过不需要使用一个数组来保存，而是3个变量prevNode,s1,s2，其中s1和s2为最终交换的节点。

prevNode为上一个节点，直接在原树上进行中序遍历，当发现顺序不对时，让s1=prevNode, s2=root，接着遍历，如果还存在顺序 不对，只需要更新s2即可。

/**
 * @来源： Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍：一个致力于帮助开发者用代码改变世界为使命的平台，每天都可以在这里找到技术世界的头条内容
 * 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) {
  let s1=null,s2=null,prev=null
  function dfs(root){
    if(root.left)dfs(root.left)
    if(prev && root.val<=prev.val){
      if(!s1)s1=prev
      if(s1)s2=root
    }
    prev=root
    if(root.right)dfs(root.right)
  }
  dfs(root)
  let t=s1.val
  s1.val=s2.val
  s2.val=t
};

扩展阅读：