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?
Solution:O(n)
public class Solution {
public void recoverTree(TreeNode root) {
if(root == null)
return;
Dao dao = new Dao();
doInorder(root, dao);
int val = dao.node1.val;
dao.node1.val = dao.node2.val;
dao.node2.val = val;
}
class Dao{
TreeNode node1;
TreeNode node2;
TreeNode preroot;
}
public void doInorder(TreeNode root,Dao dao){
if(root == null)
return ;
doInorder(root.left,dao);
if(dao.preroot == null)
dao.preroot = root;
else{
if(dao.preroot.val > root.val){
if(dao.node1 == null)
dao.node1 = dao.preroot;
dao.node2 = root;
}
dao.preroot = root;
}
doInorder(root.right,dao);
}
}
Key Concept: Use dao to store two wrong node, finally swap
沒有留言:
張貼留言