LeetCode 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/
 * @介绍：前端中文网是以前端进阶资源教程分享为主的专业网站，包括：前端、大厂面试题、typescript教程、程序人生、React.js
 * 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
};

更多题解可以访问我的 码农周刊 仓库：https://github.com/meibin08/free-programming-books， 一起学习更多前端前沿知识。