跳到主要内容

99.恢复二叉搜索树

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

题解 1 - 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);
}
}

题解 2 - 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);
}
}

题解 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);
}
}