[数据结构与算法]Leetcode99

题目描述：
二叉搜索树中的两个节点被错误地交换。
请在不改变其结构的情况下，恢复这棵树题目
思路：
抓住：只有两个节点被错误地交换这句话，我们需要找到这两个节点
第一种情况：左右各有一个非法节点，直接交换
第二种情况：左右某一边又一个，与根节点交换
如何交换
交换的本质是：将该节点的前置节点的next指针指向正确的节点，所谓原地交换，因此需要保留问题节点的前置节点

代码：

class Solution {
    
    static TreeNode prev;
    static TreeNode sn,fn;  //firstnode, secondnode
    public void recoverTree(TreeNode root) {
        
        prev=sn=fn=null;
         
        helper(root);
        
        int temp=fn.val;
        fn.val=sn.val;
        sn.val=temp;
    }
    
    public void helper(TreeNode root)
    {
        if(root==null)
        {
            return;
        }
                
        helper(root.left);
        
        if(prev!=null && prev.val>=root.val)    //1st vale inorder ke lie na chale ye
        {
            if(sn==null)
            {
                fn=prev;
            }
            sn=root;
        }
        prev=root;
        
        helper(root.right);
        
    }
}