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?  

BST:二叉查找树。根节点大于左子树所有节点，根节点小于右子树所有节点。递归定义

题意

一棵BST中有两个节点交换了，恢复这颗树

思路

1.O(N)空间复杂度

中序遍历将节点放到list中，遍历list放到int[]数组中，对int[]数组进行排序，遍历list。list.get(i).val = nums[i]

1 /** 2  * Definition for binary tree 3  * public class TreeNode { 4  *     int val; 5  *     TreeNode left; 6  *     TreeNode right; 7  *     TreeNode(int x) { val = x; } 8  * } 9  */10 import java.util.ArrayList;11 import java.util.Arrays;12 import java.util.List;13 14 public class Solution {15     List
     
       listOfInOrder = new ArrayList
      
       ();16     17     public void recoverTree(TreeNode root) {18         inOrderTravel(root);19         int nums[] = new int[listOfInOrder.size()];20         for(int i = 0; i < nums.length; i++){21             nums[i] = listOfInOrder.get(i).val;22         }//for23         24         Arrays.sort(nums);                             //对数组升序排列25         for(int i = 0; i < nums.length; i++)26             listOfInOrder.get(i).val = nums[i];27     }28     29     /**30      * 中序遍历，节点放到list中31      * @param root32      */33     private void inOrderTravel(TreeNode root){34         if(root != null){35             inOrderTravel(root.left);36             listOfInOrder.add(root);37             inOrderTravel(root.right);38         }39     }40 }
      
     

 2.O(1)空间复杂度，中序遍历递归

1 public class Solution 2 { 3     private TreeNode node1 = null; 4     private TreeNode node2 = null; 5     private TreeNode pre = null; 6  7     public void recoverTree(TreeNode root) { 8         if(root == null) 9             return;10         inOrderTravel(root);11         12         int temp = node1.val;13         node1.val = node2.val;14         node2.val = temp;15     }16 17     private void inOrderTravel(TreeNode root){18         if(root != null){19             inOrderTravel(root.left);20             if(pre != null && pre.val > root.val){21                 if(node1 == null){22                     node1 = pre;23                     node2 = root;24                 }25                     26                 node2 = root;27             }//if28             pre = root;29             inOrderTravel(root.right);30         }31     }//inOrderTravel32 33     public static void main(String args[]){34         TreeNode root = new TreeNode(1);35         TreeNode node1 = new TreeNode(2);36         TreeNode node2 = new TreeNode(3);37 38         root.right = node1;39         node1.left = node2;40 41         Solution sol = new Solution();42 43         inOrderTravelOut(root);44         System.out.println();45         sol.recoverTree(root);46         inOrderTravelOut(root);47     }48 49     private static void inOrderTravelOut(TreeNode root){50         if(root != null){51             inOrderTravelOut(root.left);52             System.out.print(root.val + " ");53             inOrderTravelOut(root.right);54         }55     }56 }