?LeetCode刷題實(shí)戰(zhàn)99：恢復(fù)二叉搜索樹(shù)
算法的重要性，我就不多說(shuō)了吧，想去大廠(chǎng)，就必須要經(jīng)過(guò)基礎(chǔ)知識(shí)和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個(gè)公眾號(hào)后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選 ！
今天和大家聊的問(wèn)題叫做?恢復(fù)二叉搜索樹(shù)，我們先來(lái)看題面：
https://leetcode-cn.com/problems/recover-binary-search-tree/
You are given the root of a binary search tree (BST), where exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.
Follow up: A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?
題意
解題
public?class?Solution?{
?
????Listlist;
?
????public?void?recoverTree(TreeNode root)?{
????????list?= new?ArrayList<>();
????????inorderTraversal(root);
????????ListtempList = new?ArrayList<>(list);
????????Collections.sort(tempList, new?Comparator() {
????????????@Override
????????????public?int?compare(TreeNode treeNode1, TreeNode treeNode2) {
????????????????return?treeNode1.val - treeNode2.val;
????????????}
????????});
????????ListwrongList = new?ArrayList<>();
????????for(int?i = 0; i < list.size(); i++){
????????????if(list.get(i).val != tempList.get(i).val){
????????????????wrongList.add(i);
????????????}
????????}
????????change(list, wrongList.get(0), wrongList.get(1));
????}
?
????private?void?inorderTraversal(TreeNode root){
????????if(root == null){
????????????return;
????????}
????????inorderTraversal(root.left);
????????list.add(root);
????????inorderTraversal(root.right);
????}
?
????private?void?change(Listlist, int?i, int?j) {
????????Integer temp = list.get(i).val;
????????list.get(i).val = list.get(j).val;
????????list.get(j).val = temp;
????}
}
上期推文：