資料結構與算法分析筆記與總結(java實作)--二叉樹9：樹上最遠距離練習題

題目：從二叉樹的節點A出發，可以向上或者向下走，但沿途的節點隻能經過一次，當到達節點B時，路徑上的節點數叫作A到B的距離。對于給定的一棵二叉樹，求整棵樹上節點間的最大距離。給定一個二叉樹的頭結點root，請傳回最大距離。保證點數大于等于2小于等于500.

思路：了解題目的含義，對于一棵以root為根的二叉樹，樹上的最大距離可能來自3中情況：

情況1：完全來自root的左子樹，如圖所示，即最大路徑不經過root結點，隻在結點1的左子樹2上面，此時的最大距離為8。

情況2：完全來自root結點的右子樹，如圖所示，最大路徑不經過root結點，隻在結點1的右側左子樹3上面，此時最大距離是9。

情況3：來自結點root的兩側，如圖所示，經過root結點，此時的最大距離=root的左子樹的高度（即結點3的最長路徑）+root右子樹的高度（即結點3的最長路徑）+root結點本身。

分析可知，要計算結點root所在子樹的最長距離，需要已知：左子樹②的最長距離LMaxLength，左子樹的高度LHeight；右子樹③的最長距離RMaxLength，右子樹的高度RHeight.然後比較Math.max(LMax,RMax,(LHeight+RHeight+1))，其最大值就是這棵二叉樹的最大距離，即對于每個子樹，需要求出它的最大距離和最大高度。顯然這就是一個遞推關系式，可以使用遞歸來實作，即設計一個遞歸函數，給定一個根結點root,求出這個根結點的最大距離max和最大高度height并傳回這2個數值。其中maxLength= Math.max(LMax,RMax,(LHeight+RHeight+1))；而由于要傳回這棵子樹的高度，如何求子樹的高度呢？二叉樹的高度就是它的2個子樹高度中的較大值再加上1，即height=Math.max(LHeight, RHeight)+1;

遞歸的遞推關系有了，關鍵是找到遞歸的起始條件或者了解為終止條件。這裡使用的思想是後序周遊（先周遊左右子樹再處理結論），聯系二叉樹的後序周遊算法，進行改編。顯然if(root==null)時:max=0;height=0;

總結：設計一個遞歸函數，輸入根結點root，求出這棵二叉樹的最大距離maxLength和高度length并傳回。遞推關系為：

maxLength= Math.max(LMax,RMax,(LHeight+RHeight+1))；

height=Math.max(LHeight, RHeight)+1

邊界條件為：

if(root==null) return max=0;height=0;

在Java中不能分開傳回2個值，是以要将2個值整合成為一個數組進行傳回即可。

importjava.util.*;

//求二叉樹上結點的最大距離：遞歸；最大值隻可能來自3中情況

publicclass LongestDistance {

    public int findLongest(TreeNode root) {

       //特殊輸入

        if(root==null) return 0;

       //調用遞歸函數來求得最大距離maxLength和高度height

        int[] results=this.process(root);

       //傳回結果

        return results[0];

    }

   //這是一個遞歸方法，用于求出一個二叉樹的最大距離和高度并傳回這2個值

    private int[] process(TreeNode root){

         int[] tempResults=new int[2];

       //邊界條件

        if(root==null){

            tempResults[0]=0;

            tempResults[1]=0;

            return tempResults;

        }

       //最大值來自3中情況，進行比較

       //左子樹的結果：

        int[]paramLeft=this.process(root.left);

        int LMaxLength=paramLeft[0];

        int LHeight=paramLeft[1];

       //右子樹的結果：

        int[] paramRight=this.process(root.right);

        int RMaxLength=paramRight[0];

        int RHeight=paramRight[1];

       //比較得到最大值和高度，并組成數組傳回,常識：Math.max()函數隻能比較2個數的大小

       //遞歸的遞推關系

       tempResults[0]=Math.max(Math.max(LMaxLength,RMaxLength),LHeight+RHeight+1);

       tempResults[1]=Math.max(LHeight,RHeight)+1;

       //帶有傳回值的遞歸函數

        return tempResults;

    }

}

常識：Math.max()函數隻能放入2個參數，即隻能比較2個數的大小，如果需要比較更多數的大小，那麼在Math.max()裡面再套用Math.max()即可。

對于遞歸方法，可以有傳回值也可以沒有傳回值，并不影響遞歸的使用，遞歸的設計應該從功能上來思考，思考這個遞歸方法需要解決一個什麼問題？需要輸入的資訊是什麼？傳回的資訊又是什麼？在這個遞歸方法中需要對下一層遞歸方法的傳回值進行怎樣的處理？（即如何遞推）；從政策上來講，就是先明确遞推關系再明确初始條件（終止條件）。