恢复二叉搜索树

/*
Morris中序遍历二叉树，空间复杂度O（1），耗时比较高。。没过测试，试了几个线下应该可以，
时间复杂度O（n），但是有些时间节点会遍历两次。
*/  import java.util.*;
public class Solution {
    public void recoverTree(TreeNode root) {
        TreeNode cur = root;
        TreeNode mostRight;
        TreeNode firstStrange=null;
        TreeNode firstStrange_next = new TreeNode(Integer.MIN_VALUE);
        TreeNode pre=new TreeNode(Integer.MIN_VALUE);
        while (cur!=null) {
            if (cur.left!=null) {
                mostRight = cur.left;
                while(mostRight.right!=null&&mostRight.right!=cur) {
                    mostRight=mostRight.right;
                }
                if (mostRight.right==null) {
                    mostRight.right=cur;
                    cur = cur.left;
                    continue;
                }
                else {
                    mostRight.right = null;
                }
            }
            if (pre.val>cur.val) {
                if (firstStrange==null) {
                    firstStrange=pre;
                    firstStrange_next=cur;
                }
                else {
                    int term = firstStrange.val;
                    firstStrange.val = cur.val;
                    cur.val = term;
                    return;
                }
            }
            pre = cur;
            cur =cur.right;
        }
        int term = firstStrange.val;
        firstStrange.val = firstStrange_next.val;
        firstStrange_next.val = term;
        return;
    }
}

//只要用到递归空间复杂度至少是O(书的高度)，所以要做到O(1)的空间复杂度，只有Morris中序遍历

public void recoverTree(TreeNode root) { if(root==null) return; TreeNode cur=root,m1=null,m2=null,last=null; while(cur!=null) { TreeNode pre=cur.left; if(pre!=null) { while(pre.right!=null&&pre.right!=cur) pre=pre.right; if(pre.right==null) { pre.right=cur; cur=cur.left; continue; } else pre.right=null; } if(last==null) last=cur; else { if(m1==null&&last.val>cur.val) { m1=last; m2=cur; } else if(m1!=null&&last.val>cur.val) m2=cur; last=cur; } cur=cur.right; }  int t=m1.val; m1.val=m2.val; m2.val=t; } 

//满足空间复杂度为常数
//思路：设定两个指针用来指向两处错误处和一个pre指针指向中序遍历的前一个结点。
public class Solution {
    TreeNode pre,mistake1,mistake2;
    public void recoverTree(TreeNode root) {
        inTraversal(root);
        mistake1.val=mistake2.val^mistake1.val^(mistake2.val=mistake1.val);
    }
    public void inTraversal(TreeNode root){
        if(root==null) return ;
        inTraversal(root.left);
        if(pre!=null&&pre.val>root.val){
            if(mistake1==null){
                mistake1=pre;
                mistake2=root;
            }else mistake2=root;
        }
        pre=root;
        inTraversal(root.right);
    }
}

import java.util.*;
public class Solution {
    public void recoverTree(TreeNode root) {
		List<TreeNode> list = new ArrayList<>();
		inorder(root, list);
		TreeNode first = null, second = null;
		for (int i = 0; i < list.size() - 1; i ++) {
			if(list.get(i).val > list.get(i + 1).val) {
				first = list.get(i);
				break;
			}
		}
		for (int i = list.size() - 1; i > 0; i --) {
			if(list.get(i).val < list.get(i - 1).val) {
				second = list.get(i);
				break;
			}
		}
		first.val = second.val ^ first.val ^ (second.val = first.val);
	}
	public static void inorder(TreeNode root, List<TreeNode> list) {
		if(root != null) {
			inorder(root.left, list);
			list.add(root);
			inorder(root.right, list);
		}
	}
}

public void recoverTree(TreeNode root) {
        TreeNode pre = null;
        TreeNode first = null, second = null;
        // Morris Traversal
        TreeNode temp = null;
		while(root!=null){ if(root.left!=null){
				// connect threading for root temp = root.left;
				while(temp.right!=null && temp.right != root) temp = temp.right;
				// the threading already exists if(temp.right!=null){ if(pre!=null && pre.val > root.val){ if(first==null){first = pre;second = root;} else{second = root;}
				    } pre = root;
				    
					temp.right = null; root = root.right;
				}else{
					// construct the threading
					temp.right = root; root = root.left;
				}
			}else{ if(pre!=null && pre.val > root.val){ if(first==null){first = pre;second = root;} else{second = root;}
				} pre = root; root = root.right;
			}
		}
		// swap two node values; if(first!= null && second != null){
		    int t = first.val;
		    first.val = second.val;
		    second.val = t;
		}
    }

public class Solution {
    
    TreeNode firstElement = 
    
    TreeNode firstElement = null;
    TreeNode secondElement = 
    TreeNode secondElement = null;
    
    // The reason for this initialization is to avoid null pointer exception in the first comparison when prevElement has not been initialized
    TreeNode prevElement = new TreeNode(Integer.MIN_VALUE);
    
    
    
    public void recoverTree(TreeNode root) {
        
        
        
        // In order traversal to find the two elements
        traverse(root);
        
        // Swap the values of the two nodes
        int temp = firstElement.val;
        firstElement.
        firstElement.val = secondElement.val;
        secondElement.
        secondElement.val = temp;
    }
    
    
    }
    
    private void traverse(TreeNode root) {
        
        
        
        if (root == null)
            
            return;
            
        traverse(root.left);
        
        
            
        traverse(root.left);
        
        // Start of "do some business", 
        // If first element has not been found, assign it to prevElement (refer to 6 in the example above)
        if (firstElement == null && prevElement.val >= root.val) {
            firstElement = prevElement;
        }
    
        
            firstElement = prevElement;
        }
    
        // If first element is found, assign the second element to the root (refer to 2 in the example above)
        if (firstElement != null && prevElement.val >= root.val) {
            secondElement = root;
        }        
        prevElement = root;

        
            secondElement = root;
        }        
        prevElement = root;
        // End of "do some business"
        traverse(root.right);
}