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 arr = new ArrayList (); List treeList = new ArrayList (); 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 arr, List 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 chs) { if (root == null) { chs.add('#'); return; } List list = new ArrayList (); 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 chars = new ArrayList (); recoverBinarySearchTree.binarySearchTreeToArray(recoverBinarySearchTree.recover(recoverBinarySearchTree.createTree(tree)), chars); System.out.println(Arrays.toString(chars.toArray(new Character[chars.size()]))); chars = new ArrayList (); recoverBinarySearchTree.binarySearchTreeToArray(recoverBinarySearchTree.recoverTree(recoverBinarySearchTree.createTree(tree)), chars); System.out.println(Arrays.toString(chars.toArray(new Character[chars.size()]))); }}