1. Title
Recover Binary Search Tree
2. Http address
https://leetcode.com/problems/recover-binary-search-tree/
3. The question
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.
4. My code (AC)
1 void recoverTreeHelp(TreeNode root,TreeNode input []) { 2 3 if ( root == null) 4 return; 5 6 recoverTreeHelp(root.left, input); 7 8 if ( input[2] != null) 9 { 10 if ( input[2].val > root.val){ 11 input[1] = root; 12 input[0] = input[0] != null ? input[0] : input[2]; 13 } 14 } 15 16 input[2] = root; 17 18 recoverTreeHelp(root.right,input); 19 return; 20 } 21 22 public void recoverTree(TreeNode root) { 23 24 TreeNode input [] = new TreeNode[3]; 25 recoverTreeHelp(root, input); 26 if( input[0] != null && input[1] != null) 27 { 28 int tmp = input[0].val; 29 input[0].val = input[1].val; 30 input[1].val = tmp; 31 } 32 }
原文：http://www.cnblogs.com/ordili/p/4928462.html