LintCode：691.二叉搜尋樹交換節點

題目：

分析：

• 因為是二叉搜尋樹，是以最直覺的做法就是采取中序周遊，得到有序的數列，其中肯定存在兩處逆序，我們需要做的是把逆序部分交換使得該序列是遞增的。
• 比如題中的例子，上面的二叉樹中序周遊結果為 15342，存在逆序對53和42，而下面的二叉樹序列為12345，我們隻需要把第一個逆序對的第一個數字和第二個逆序對的第二個數字交換即可得到12345。
• 另外，找到這兩個被交換的節點後，隻需要改變這兩個節點的值即可達到交換的目的，并不需要改變結構。

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root: the given tree
     * @return: the tree after swapping
     */
    TreeNode pre;
    TreeNode p1,p2;
    public TreeNode bstSwappedNode(TreeNode root) {
        // write your code here
        if(root==null)  return null;
        pre=p1=p2=null;
        InOrder(root);
        if(pre!=null && p1!=null && p2!=null){
            int temp=p1.val;   //隻需要交換節點的值即可
            p1.val=p2.val;
            p2.val=temp;
        }
        return root;
    }

    //中序周遊
    private  void InOrder(TreeNode root){
        if(root==null)  return;
        InOrder(root.left);
        if(pre!=null && pre.val>root.val){
            if(p1==null){
                p1=pre;
            }
            p2=root;
        }
        pre=root;
        InOrder(root.right);
    }
}