leetcode — recover-binary-search-tree

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;/**
* Source : https://oj.leetcode.com/problems/recover-binary-search-tree/
*
*
* Two elements of a binary search tree (BST) are swapped by mistake.
*
* Recover the tree without changing its structure.
*
* Note:
* A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?
*
* confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.
*
* OJ's Binary Tree Serialization:
*
* The serialization of a binary tree follows a level order traversal, where '#' signifies
* a path terminator where no node exists below.
*
* Here's an example:
*
* 1
* / \
* 2 3
* /
* 4
* \
* 5
*
* The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".
*/
public class RecoverBinarySearchTree { private TreeNode n1;
private TreeNode n2;
private TreeNode pre; /**
* 搜索二叉树
* 将错误调换位置的两个元素恢复位置
*
* 先中序遍历树，将节点的value放到一个数组中，并将节点也放到一个数组中
* 然后将value数组排序
* 然后依次赋值给节点数组中每个节点，然后将节点数组恢复成一棵树
* 占用空间为O(n)
*
* @param root
* @return
*/
public TreeNode recover (TreeNode root) {
List<Integer> arr = new ArrayList<Integer>();
List<TreeNode> treeList = new ArrayList<TreeNode>();
traverseInorder(root, arr, treeList);
Collections.sort(arr);
for (int i = 0; i < arr.size(); i++) {
treeList.get(i).value = arr.get(i);
}
return root; } public void traverseInorder (TreeNode root, List<Integer> arr, List<TreeNode> treeList) {
if (root == null) {
return ;
}
traverseInorder(root.leftChild, arr, treeList);
arr.add(root.value);
treeList.add(root);
traverseInorder(root.rightChild, arr, treeList);
} /**
* 二叉搜索树：中序遍历的时候是单调递增的
*
* 中序遍历树，将树遍历为一个链表，当前节点的值一定大于上一个节点的值，否则就是被调换的节点，中序遍历的时候记录调换的两个节点
* 因为只有两个节点被置换，所以如果是第一次出现上一个节点的值大于当前节点，说明是被换到其前面的节点，所以被置换的是上一个节点
* 如果是第二次出现上一个节点的值大于当前节点，那么当前节点是被置换的节点
* 中序遍历完成后，调换记录的两个节点的值，就恢复了二叉搜索树
*
* @param root
* @return
*/
public TreeNode recoverTree (TreeNode root) {
traverseInorder(root);
if (n1 != null && n2 != null) {
int temp = n1.value;
n1.value = n2.value;
n2.value = temp;
}
return root;
} public void traverseInorder (TreeNode root) {
if (root == null) {
return;
}
traverseInorder(root.leftChild);
if (pre != null) {
if (pre.value > root.value) {
if (n1 == null) {
n1 = pre;
}
n2 = root;
}
}
pre = root;
traverseInorder(root.rightChild);
} public TreeNode createTree (char[] treeArr) {
TreeNode[] tree = new TreeNode[treeArr.length];
for (int i = 0; i < treeArr.length; i++) {
if (treeArr[i] == '#') {
tree[i] = null;
continue;
}
tree[i] = new TreeNode(treeArr[i]-'0');
}
int pos = 0;
for (int i = 0; i < treeArr.length && pos < treeArr.length-1; i++) {
if (tree[i] != null) {
tree[i].leftChild = tree[++pos];
if (pos < treeArr.length-1) {
tree[i].rightChild = tree[++pos];
}
}
}
return tree[0];
} /**
* 使用广度优先遍历将树转化为数组
*
* @param root
* @param chs
*/
public void binarySearchTreeToArray (TreeNode root, List<Character> chs) {
if (root == null) {
chs.add('#');
return;
}
List<TreeNode> list = new ArrayList<TreeNode>();
int head = 0;
int tail = 0;
list.add(root);
chs.add((char) (root.value + '0'));
tail ++;
TreeNode temp = null; while (head < tail) {
temp = list.get(head);
if (temp.leftChild != null) {
list.add(temp.leftChild);
chs.add((char) (temp.leftChild.value + '0'));
tail ++;
} else {
chs.add('#');
}
if (temp.rightChild != null) {
list.add(temp.rightChild);
chs.add((char)(temp.rightChild.value + '0'));
tail ++;
} else {
chs.add('#');
}
head ++;
} //去除最后不必要的
for (int i = chs.size()-1; i > 0; i--) {
if (chs.get(i) != '#') {
break;
}
chs.remove(i);
}
} private class TreeNode {
TreeNode leftChild;
TreeNode rightChild;
int value; public TreeNode(int value) {
this.value = value;
} public TreeNode() {
}
} public static void main(String[] args) {
RecoverBinarySearchTree recoverBinarySearchTree = new RecoverBinarySearchTree();
char[] tree = new char[]{'3','4','5','#','#','2'};
List<Character> chars = new ArrayList<Character>();
recoverBinarySearchTree.binarySearchTreeToArray(recoverBinarySearchTree.recover(recoverBinarySearchTree.createTree(tree)), chars);
System.out.println(Arrays.toString(chars.toArray(new Character[chars.size()]))); chars = new ArrayList<Character>();
recoverBinarySearchTree.binarySearchTreeToArray(recoverBinarySearchTree.recoverTree(recoverBinarySearchTree.createTree(tree)), chars);
System.out.println(Arrays.toString(chars.toArray(new Character[chars.size()])));
}}