題目來(lái)源：?？途W(wǎng)

題目描述：

有一棵二叉樹(shù)，樹(shù)上每個(gè)點(diǎn)標(biāo)有權(quán)值，權(quán)值各不相同，請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法算出權(quán)值最大的葉節(jié)點(diǎn)到權(quán)值最小的葉節(jié)點(diǎn)的距離。二叉樹(shù)每條邊的距離為1，一個(gè)節(jié)點(diǎn)經(jīng)過(guò)多少條邊到達(dá)另一個(gè)節(jié)點(diǎn)為這兩個(gè)節(jié)點(diǎn)之間的距離。
給定二叉樹(shù)的根節(jié)點(diǎn)root，請(qǐng)返回所求距離。

????關(guān)于下面的代碼，我是沒(méi)有寫(xiě)出的，一開(kāi)始的方向弄錯(cuò)了，看成了尋找權(quán)值最大的節(jié)點(diǎn)到最小的節(jié)點(diǎn)路徑。后面看討論區(qū)的時(shí)候，看到一個(gè)大神寫(xiě)的代碼，恍然大悟。
????原來(lái)所求的是葉節(jié)點(diǎn)，他所用的方式給根節(jié)點(diǎn)、左子樹(shù)和右子樹(shù)編號(hào)，然后進(jìn)行先序遍歷，每次遞歸時(shí)，把編號(hào)添加到字符中，當(dāng)找到葉節(jié)點(diǎn)時(shí)，再跟最大值、最小值比較。
????當(dāng)先序遍歷完成之后，再對(duì)最大值跟最小值記錄的路徑就行逐個(gè)字符比較，如果不相同就結(jié)束對(duì)比，記錄下此時(shí)的長(zhǎng)度，然后去掉，返回兩者去掉之后的和，即為所求的距離。

代碼實(shí)現(xiàn)

//典型的二進(jìn)制編碼題，算出葉子節(jié)點(diǎn)二進(jìn)制編碼，再比編碼，計(jì)算后綴長(zhǎng)度和
import java.util.*;

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}*/
public class Tree {
    private int max=0;
    private int min=99999;
    private StringBuilder maxcodec;
    private StringBuilder mincodec;
        void PreOrder(TreeNode T,char code,StringBuilder codec){
        if(T!=null){           
            codec.append(code);
            if(T.left==null && T.right==null)
            {
                if(max<T.val)
                {
                    max=T.val;
                    maxcodec = codec;
                }
                 
                if(min>T.val)
                {
                    min=T.val;
                    mincodec = codec;
                }
            }
            PreOrder(T.left,'0',new StringBuilder(codec));
            PreOrder(T.right,'1',new StringBuilder(codec));
        }
    }
    public int getDis(TreeNode root) {
        PreOrder(root,'0',new StringBuilder());
        int index=0;
        for(index=0; index<(maxcodec.length()>mincodec.length()?maxcodec.length():mincodec.length());index++)
        {
            if(maxcodec.charAt(index)!=mincodec.charAt(index))
                break;
        }
        return (maxcodec.substring(index).length()+mincodec.substring(index).length());
     
        // write code here
    }
}