99.恢复二叉搜索树

链接：99.恢复二叉搜索树
难度：Medium
标签：树、深度优先搜索、二叉搜索树、二叉树
简介：二叉搜索树中的两个节点被错误地交换。

题解 1 - typescript

• 编辑时间：2020-08-08
• 执行用时：192ms
• 内存消耗：48MB
• 编程语言：typescript
• 解法介绍：排序值替换。

function recoverTree(root: TreeNode | null): void {
  if (root === null) return;
  const list: TreeNode[] = [];
  inorder(root);
  for (let i = 0, len = list.length; i < len - 1; i++) {
    for (let j = 0; j < len - 1 - i; j++) {
      if (list[j].val > list[j + 1].val) swap(list[j], list[j + 1]);
    }
  }
  function swap(n1: TreeNode, n2: TreeNode) {
    const num = n1.val;
    n1.val = n2.val;
    n2.val = num;
  }
  function inorder(node: TreeNode | null): void {
    if (node === null) return;
    inorder(node.left);
    list.push(node);
    inorder(node.right);
  }
}

题解 2 - java

• 编辑时间：2020-02-24
• 执行用时：4ms
• 内存消耗：40.9MB
• 编程语言：java
• 解法介绍：中序遍历后查看顺序不一的值。

class Solution {
    ArrayList<TreeNode> list = new ArrayList<TreeNode>();
	public void recoverTree(TreeNode root) {
		if(root==null)return;
		inorder(root);
		TreeNode node1=null,node2=null;
		for(int i=0,len=list.size()-1;i<len;i++) {
			if(list.get(i+1).val<list.get(i).val) {
				if(node1==null) {
				    node1=list.get(i);
					node2=list.get(i+1);
				}else{
					node2=list.get(i+1);
                }
			}
		}
		int temp=node1.val;
		node1.val=node2.val;
		node2.val=temp;
    }
	public void inorder(TreeNode node) {
		if (node.left != null)
			inorder(node.left);
		list.add(node);
		if (node.right != null)
			inorder(node.right);
	}
}

题解 3 - typescript

• 编辑时间：2021-08-20
• 执行用时：144ms
• 内存消耗：47.5MB
• 编程语言：typescript
• 解法介绍：中序排序后比较。

function recoverTree(root: TreeNode | null): void {
  if (root === null) return;
  const q: TreeNode[] = [];
  inorder(root);
  let n1!: TreeNode;
  let n2!: TreeNode;
  for (let i = 1; i < q.length; i++) {
    if (q[i].val < q[i - 1].val) {
      if (n1) {
        n2 = q[i];
      } else {
        n1 = q[i - 1];
        n2 = q[i];
      }
    }
  }
  [n1.val, n2.val] = [n2.val, n1.val];
  function inorder(node: TreeNode | null) {
    if (node === null) return;
    inorder(node.left);
    q.push(node);
    inorder(node.right);
  }
}