資料結構與算法分析筆記與總結(java實作)--二叉樹8：尋找錯誤結點練習題

題目：一棵二叉樹原本是搜尋二叉樹，但是其中有兩個節點調換了位置，使得這棵二叉樹不再是搜尋二叉樹，請找到這兩個錯誤節點并傳回他們的值。保證二叉樹中結點的值各不相同。給定一棵樹的根結點，請傳回兩個調換了位置的值，其中小的值在前。

思路：對于搜尋二叉樹，總是與中序周遊關聯起來的，根據搜尋二叉樹的特點，如果一棵樹是搜尋二叉樹，那麼當對其進行中序周遊時一定是順序排列的，本題中說一棵搜尋二叉樹中的2個結點交換了位置，而由于已知各個結點各不相同是以顯然對此時的二叉樹進行中序周遊時會出現逆序的結點，即某個結點可能比前一個結點小，這種情況可能出現1次或者2次，例如12345，如果不相鄰的元素24交換位置得到14325，那麼顯然會出現2次減小的情況，4à3和3à2；如果是相鄰的2個元素23交換位置得到13245，那麼隻有1次減小的情況，3à2，是以按照中序周遊的順序周遊目前的二叉樹，每次記錄上一個數和目前的數進行比較，如果減小了就是出錯的數，記第一次出錯時的較大值（目前值的前面一個值）為number1，較小值（目前值）為number2，然後繼續向下周遊，如果遇到第2次出錯的情況，就用較小的值（目前值）替換number2，表示這才是與number1交換的值，最後顯然number1，number2就是交換的2個值，并且number1>number 2，由于要求傳回時較小的值在前面，是以傳回number2，number1。可以使用遞歸也可以不使用遞歸來解決問題。

總的來說第一個出錯的數（大）是第一次減小時前面的數；第二個出錯的數（小）是最後一次減小時後面的數。

importjava.util.*;

publicclass FindErrorNode {

    public int[] findError(TreeNode root) {

       //特殊輸入

        if(root==null) return null;

       //建立一個數組用來記錄結果,Java中數組是對象，可以引用傳遞

        int[] numbers=new int[2];

       //求出中序周遊的第一個結點最好不要使用Integer.MIN_VALUE

        node=root;

        while(node.left!=null){

            node=node.left;

        }

        lastNodeVal=node.val;

       //調用遞歸方法進行中序周遊

        this.inOrder(root,numbers);

 //傳回結果即可，注意需要小的值在前,調整順序,可以不調整，後面numbers[0]與numbers[1]互換即可

        int temp=numbers[0];

        numbers[0]=numbers[1];

        numbers[1]=temp;

        return numbers;

    }

   //成員變量lastNode，取二叉樹的中序周遊第一個結點作為lastNode

    TreeNode node=null;

   //遞歸方法，對二叉樹進行中序周遊并找出減小的2個數

    private void inOrder(TreeNode root,int[]numbers){

       //遞歸的邊界條件

        if(root==null) return;

       //①先周遊左子樹

        this.inOrder(root.left,numbers);

       //②周遊中間結點（與前面一個周遊的結點進行比較）

        if(root.val<lastNodeVal){

            if(flag==0){

                numbers[0]=lastNodeVal;

                flag=1;

            }

            //此時是錯誤的第二個數，它始終是最後一次減小時的後面的一個數

            numbers[1]=root.val;

        }

       //如果目前值比前一個值大顯然要更新lastNodeVal

        lastNodeVal=root.val;

       //③繼續周遊右子樹

        this.inOrder(root.right,numbers);

    }

}