劍指offer｜51-60題解題思路及代碼(Java版)

劍指offer51到60題總覽：

構(gòu)建乘積數(shù)組
正則表達(dá)式匹配
表示數(shù)值的字符串
字符流中第一個(gè)不重復(fù)的字符
鏈表中環(huán)的入口結(jié)點(diǎn)
刪除鏈表中重復(fù)的結(jié)點(diǎn)
二叉樹的下一個(gè)結(jié)點(diǎn)
對稱的二叉樹
按之字形打印二叉樹
把二叉樹打印成多行

51功戚、構(gòu)建乘積數(shù)組

題目描述

給定一個(gè)數(shù)組A[0,1,...,n-1],請構(gòu)建一個(gè)數(shù)組B[0,1,...,n-1],其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]娶眷。不能使用除法。

解題思路

劍指offer｜51題構(gòu)建乘積數(shù)組

兩次遍歷啸臀，第一次計(jì)算下三角届宠，第二次計(jì)算上三角。比如計(jì)算下三角，設(shè)置一個(gè)temp豌注，temp=A[0]伤塌，將temp賦值給B[1]；temp=temp*A[1]幌羞，將temp賦值給B[2]寸谜。

import java.util.ArrayList;
public class Solution {
    public int[] multiply(int[] A) {
        int[] B = new int[A.length];
        if(A.length == 0){return B;}
        if(A.length == 1){
            B[0] = 1;
            return B;
        }
        B[0] = 1;//先將B[0]賦值為1，計(jì)算下三角時(shí)用不到B[0]
        int temp = 1;//用來保存當(dāng)前乘積
        for(int i=1; i<A.length; i++){//計(jì)算下三角
            temp = temp * A[i-1];
            B[i] = temp;
        }
        temp = 1;//計(jì)算上三角前將temp置為0
        for(int i=A.length-2; i>=0; i--){//計(jì)算上三角
            temp = temp * A[i+1];
            B[i] *= temp;//B[i]應(yīng)該在計(jì)算完下三角的基礎(chǔ)上乘temp
        }
        return B;
    }
}

52属桦、正則表達(dá)式匹配

題目描述

請實(shí)現(xiàn)一個(gè)函數(shù)用來匹配包括'.'和'*'的正則表達(dá)式熊痴。模式中的字符'.'表示任意一個(gè)字符，而'*'表示它前面的字符可以出現(xiàn)任意次（包含0次）聂宾。在本題中果善，匹配是指字符串的所有字符匹配整個(gè)模式。例如系谐，字符串"aaa"與模式"a.a"和"ab*ac*a"匹配巾陕，但是與"aa.a"和"ab*a"均不匹配。

解題思路

考慮各種情況：

如果strIndex和patternIndex都到尾了纪他，則匹配成功鄙煤。
如果strIndex沒有到尾，但patternIndex已經(jīng)到尾了茶袒，str還有最后一部分沒有匹配完梯刚，則匹配失敗。
如果遇到pattern當(dāng)前字符的下一個(gè)字符是*薪寓，有幾種情況：

pattern當(dāng)前字符是.亡资，則可視作匹配0個(gè)字符，strIndex+0向叉，patternIndex+2锥腻，繼續(xù)遞歸；可視作匹配1個(gè)字符母谎，strIndex+1瘦黑，patternIndex+2，繼續(xù)遞歸奇唤；可視作暫時(shí)匹配1個(gè)字符供璧，patternIndex不移動(dòng)，后面可再選擇匹配0個(gè)或1個(gè)或再暫時(shí)匹配一個(gè)字符冻记，strIndex+1，patternIndex+0来惧，繼續(xù)遞歸冗栗。
pattern當(dāng)前字符不是.而是一個(gè)字母或者其他，則要看pattern當(dāng)前字符和str當(dāng)前字符是否一樣：不一樣，則匹配失斢缇印钠至；一樣，則和pattern當(dāng)前字符是.一樣胎源，可以選擇匹配0個(gè)或1個(gè)或暫時(shí)匹配一個(gè)字符棉钧，繼續(xù)遞歸。
3.1

public class Solution {
    public boolean match_1(char[] str, char[] pattern) {
        if (str == null || pattern == null) {
            return false;
        }
        int strIndex = 0;
        int patternIndex = 0;
        return matchCore(str, strIndex, pattern, patternIndex);
    }

    public boolean matchCore(char[] str, int strIndex, char[] pattern, int patternIndex) {
        //有效性檢驗(yàn)：str到尾涕蚤，pattern到尾宪卿，匹配成功
        if (strIndex == str.length && patternIndex == pattern.length) {
            return true;
        }
        //pattern先到尾，匹配失敗
        if (strIndex != str.length && patternIndex == pattern.length) {
            return false;
        }
        //模式第2個(gè)是*万栅，則分兩種情況佑钾，一種是*前面是.一種是*是一般字符。
        //如果是一般字符烦粒，則又可分為pattern當(dāng)前字符與str當(dāng)前字符匹配成功和不匹配兩種情況
        //而*前面是.和pattern當(dāng)前字符與str當(dāng)前字符匹配成功的情況可以寫到一起休溶。
        if (patternIndex + 1 < pattern.length && pattern[patternIndex + 1] == '*') {
            if ((strIndex != str.length && pattern[patternIndex] == str[strIndex])
                    || (strIndex != str.length && pattern[patternIndex] == '.')) {
                //*前面是.，或*前面的一般字符是與str的當(dāng)前字符匹配成功
                return matchCore(str, strIndex, pattern, patternIndex + 2) //模式后移2扰她，視為x*匹配0個(gè)字符
                        || matchCore(str, strIndex + 1, pattern, patternIndex + 2) //視為模式匹配1個(gè)字符兽掰，模式向后移動(dòng)兩位
                        || matchCore(str, strIndex + 1, pattern, patternIndex); //當(dāng)前只匹配1個(gè)，模式?jīng)]有移動(dòng)徒役，再遞歸可匹配str中的下一個(gè)或匹配0個(gè)
            } else {
                //*前面的字符與當(dāng)前字符不匹配孽尽，模式向后移動(dòng)兩位
                return matchCore(str, strIndex, pattern, patternIndex + 2);
            }
        }
        //模式第2個(gè)不是*，且字符串第1個(gè)跟模式第1個(gè)匹配廉涕，則都后移1位泻云，否則直接返回false
        if ((strIndex != str.length && pattern[patternIndex] == str[strIndex])
                || (strIndex != str.length && pattern[patternIndex] == '.')) {
            return matchCore(str, strIndex + 1, pattern, patternIndex + 1);
        }
        return false;
    }
}

53、表示數(shù)值的字符串

題目描述

請實(shí)現(xiàn)一個(gè)函數(shù)用來判斷字符串是否表示數(shù)值（包括整數(shù)和小數(shù)）狐蜕。例如宠纯，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示數(shù)值。但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是层释。

解題思路

用正則表達(dá)式婆瓜。

public class Solution {
    public boolean isNumeric(char[] str) {
        String s = String.valueOf(str);
        return s.matches("[\\+-]?[0-9]*(\\.[0-9]*)?([eE][\\+-]?[0-9]+)?");
    }
}

54、字符流中第一個(gè)不重復(fù)的字符

題目描述

請實(shí)現(xiàn)一個(gè)函數(shù)用來找出字符流中第一個(gè)只出現(xiàn)一次的字符贡羔。例如廉白，當(dāng)從字符流中只讀出前兩個(gè)字符"go"時(shí)，第一個(gè)只出現(xiàn)一次的字符是"g"乖寒。當(dāng)從該字符流中讀出前六個(gè)字符“google"時(shí)再愈，第一個(gè)只出現(xiàn)一次的字符是"l"膳凝。
輸出描述:
如果當(dāng)前字符流沒有存在出現(xiàn)一次的字符，返回#字符。

public class Solution {
    int arr[] = new int[256];//建立所有可能字符的數(shù)組
    int index;
    public Solution(){
        for(int i=0; i<arr.length; i++){//將數(shù)組所有值賦值為-1
            arr[i] = -1;
        }
        index = 0;//index為當(dāng)前插入的字符的個(gè)數(shù)
    }
    //Insert one char from stringstream
    public void Insert(char ch)//因?yàn)橐l繁插入，所以不建議在insert方法中設(shè)置循環(huán)
    {
        if(arr[ch] == -1){//-1表示之前沒有出現(xiàn)過，現(xiàn)在出現(xiàn)了
            arr[ch] = index;//將對應(yīng)字符的位賦值為字符流的index
        }else if(arr[ch] >= 0){//>=0表示之前出現(xiàn)過一次，而且是唯一一次，而此時(shí)出現(xiàn)了第二次
            arr[ch] = -2;//出現(xiàn)了第二次谆膳，將對應(yīng)字符的位賦值為-2，>=0的情況只保存當(dāng)前只出現(xiàn)了一次撮躁，并記錄在字符流中的index
        }
        index++;//插入了一個(gè)字符漱病，index+1
    }
    //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
        int result_index = index;//給返回結(jié)果一個(gè)初始值
        for(int i=0; i<arr.length; i++){//遍歷數(shù)組
            if(arr[i] >= 0){//遇到一個(gè)只出現(xiàn)一次的字符
                if(result_index == index){result_index = i;}//如果是第一個(gè)只出現(xiàn)一次的字符，則將result_index更新
                else{
                    if(arr[i] < arr[result_index]){//找到了新的只出現(xiàn)一次的字符把曼，且其保存的字符流的位置更靠前杨帽，更新result_index。
                        result_index = i;
                    }
                }
            }
        }
        if(result_index == index){return '#';}//如果整個(gè)遍歷沒有找到只出現(xiàn)一次的字符祝迂，返回#
        else{return (char)result_index;}//將int類型的下標(biāo)轉(zhuǎn)化為char類型
    }
}

55睦尽、鏈表中環(huán)的入口結(jié)點(diǎn)

題目描述

給一個(gè)鏈表，若其中包含環(huán)型雳，請找出該鏈表的環(huán)的入口結(jié)點(diǎn)当凡，否則，輸出null纠俭。

解題思路

方法很多沿量，記錄兩種，都是快慢指針的思想冤荆。設(shè)置一個(gè)慢指針slow朴则，一次走一步；設(shè)置一個(gè)快指針fast钓简，一次走兩步乌妒。如果存在環(huán)，則快慢指針一定會(huì)在環(huán)內(nèi)相遇外邓。如果不存在環(huán)撤蚊，則fast會(huì)率先走到鏈表尾，則返回null损话。在環(huán)內(nèi)相遇之后侦啸，有兩種方法尋找入環(huán)結(jié)點(diǎn)：

從快慢指針相遇的結(jié)點(diǎn)開始，fast結(jié)點(diǎn)不走丧枪，slow再走一圈光涂，得到環(huán)內(nèi)包含的結(jié)點(diǎn)數(shù)c。然后令p1=pHead拧烦，p1先走c步(此時(shí)已經(jīng)知道有環(huán)忘闻，不用擔(dān)心會(huì)走到空結(jié)點(diǎn))，令p2=pHead恋博，然后p1和p2一起走服赎，每次都走一步(p1始終超前p2 c步)葵蒂。則他們第一次相等的時(shí)候指向的節(jié)點(diǎn)，就是入環(huán)結(jié)點(diǎn)重虑。
從快慢指針相遇的結(jié)點(diǎn)開始，我們有以下推導(dǎo)：
參考鏈接：https://www.nowcoder.com/questionTerminal/253d2c59ec3e4bc68da16833f79a38e4

劍指offer｜55題鏈表中環(huán)的入口結(jié)點(diǎn)

假設(shè)x為環(huán)前面的路程（黑色路程）秦士，a為環(huán)入口到相遇點(diǎn)的路程（藍(lán)色路程缺厉，假設(shè)順時(shí)針走）， c為環(huán)的長度（藍(lán)色+橙色路程）
當(dāng)快慢指針相遇的時(shí)候：
此時(shí)慢指針走的路程為 $S_{slow}= x + m * c + a$ 隧土， $m$ 為慢指針在環(huán)內(nèi)轉(zhuǎn)的圈數(shù)提针，這個(gè)圈數(shù)并不重要。
快指針走的路程為 $S_{fast} = x + n * c + a$ 曹傀， $n$ 為快指針在環(huán)內(nèi)轉(zhuǎn)的圈數(shù)辐脖。
我們設(shè)置快指針一次走兩步，慢指針一次走一步皆愉，則相遇時(shí)他們的路程有如下關(guān)系： $2S_{slow} = S_{fast}$
則有： $2 * ( x + m*c + a ) = (x + n *c + a)$
從而可以推導(dǎo)出： $\begin{aligned} x &= (n - 2 * m )*c - a\\ &= (n - 2 *m -1 )*c + c - a \end{aligned}$
上式第二步中嗜价，我們提出一個(gè) $c$ ，則 $c-a$ 可以表示相遇點(diǎn)后幕庐，環(huán)后面部分的路程久锥。（橙色路程）
所以，我們可以讓一個(gè)指針p從起點(diǎn)A開始走异剥，讓slow指針從相遇點(diǎn)B開始繼續(xù)往后走瑟由，p和slow指針?biāo)俣纫粯樱看沃蛔咭徊皆┦伲瑒t當(dāng)指針p走到環(huán)入口點(diǎn)的時(shí)候（此時(shí)剛好走了x）slow指針也一定剛好到達(dá)環(huán)入口點(diǎn)歹苦。p和slow恰好相遇在環(huán)的入口點(diǎn)。返回p或slow即可督怜。這種方法需要一點(diǎn)推導(dǎo)所以可能想不到殴瘦，但是推出來之后寫代碼就變得更簡單了。

public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead){
        if(pHead==null || pHead.next==null || pHead.next.next==null){return null;}
        ListNode slow = pHead.next;//slow先走一步
        ListNode fast = pHead.next.next;//fast先走兩步
        while(slow != fast){//當(dāng)還沒有相遇的時(shí)候
            if(fast.next!=null && fast.next.next!=null){//沒有走到鏈表尾
                slow = slow.next;//slow和fast繼續(xù)走
                fast = fast.next.next;
            }else{//如果走到了鏈表尾亮蛔，則一定沒有環(huán)痴施，直接返回null
                return null;
            }
        }//循環(huán)出來了一定是slow和fast相遇了
        ListNode p = pHead;//p指向鏈表頭，與slow一起走究流，p和slow一次都只走一步
        while(p!=slow){//p和slow一起走辣吃，此時(shí)有環(huán)則他們一定會(huì)在入環(huán)結(jié)點(diǎn)相遇。
            p = p.next;
            slow = slow.next;
        }
        return p;
    }
}

56芬探、刪除鏈表中重復(fù)的結(jié)點(diǎn)

題目描述

在一個(gè)排序的鏈表中神得，存在重復(fù)的結(jié)點(diǎn)，請刪除該鏈表中重復(fù)的結(jié)點(diǎn)偷仿，重復(fù)的結(jié)點(diǎn)不保留哩簿，返回鏈表頭指針宵蕉。例如，鏈表1->2->3->3->4->4->5 處理后為 1->2->5

解題思路

如果鏈表最前面就有重復(fù)的节榜，則將鏈表頭前面的重復(fù)結(jié)點(diǎn)全部跳過羡玛，讓pHead指向第一個(gè)不重復(fù)的結(jié)點(diǎn)，返回新的頭結(jié)點(diǎn)宗苍。如果鏈表最前面不是重復(fù)的稼稿，則找到最后一個(gè)不重復(fù)結(jié)點(diǎn)，遞歸刪除后面的重復(fù)結(jié)點(diǎn)讳窟。這里不加速找到最后一個(gè)不重復(fù)的結(jié)點(diǎn)也可以让歼，如果頭結(jié)點(diǎn)不是重復(fù)結(jié)點(diǎn)，則遞歸頭結(jié)點(diǎn)后面的結(jié)點(diǎn)丽啡，直到遞歸到頭結(jié)點(diǎn)就是重復(fù)結(jié)點(diǎn)谋右。

public class Solution {
    public ListNode deleteDuplication(ListNode pHead){
        if(pHead == null){return null;}
        if(pHead.next == null){return pHead;}
        ListNode p = pHead;
        if(p.val == p.next.val){//如果p點(diǎn)與p后面的結(jié)點(diǎn)重復(fù)
            while(p.next!=null && p.val == p.next.val){//跳過所有的重復(fù)結(jié)點(diǎn)，直到p結(jié)點(diǎn)不重復(fù)补箍，或者p為最后一個(gè)結(jié)點(diǎn)改执。
                p = p.next;//如果p為重復(fù)結(jié)點(diǎn)，且p后面還有結(jié)點(diǎn)馏予，則p后移一位
            }
            pHead = deleteDuplication(p.next);//如果是p和p后面的結(jié)點(diǎn)不重復(fù)了天梧，則遞歸p.next；或者p為最后一個(gè)結(jié)點(diǎn)了霞丧，但是p結(jié)點(diǎn)是重復(fù)結(jié)點(diǎn)呢岗，依舊遞歸p.next，這時(shí)遞歸返回null
        }else{//如果p不是重復(fù)結(jié)點(diǎn)蛹尝，則看p的后面的結(jié)點(diǎn)是不是重復(fù)結(jié)點(diǎn)
            while(p.next.next!=null && p.next.val != p.next.next.val){//向后找重復(fù)結(jié)點(diǎn)后豫，p指向最后一個(gè)不重復(fù)結(jié)點(diǎn)
                p = p.next;
            }//這里的循環(huán)不要也可以，直接p.next = deleteDuplication(p.next);也行
            p.next = deleteDuplication(p.next);//遞歸刪除p結(jié)點(diǎn)后面的重復(fù)結(jié)點(diǎn)突那，并將刪除后返回的頭結(jié)點(diǎn)連接到p的后面
        }
        return pHead;
    }
}

57挫酿、二叉樹的下一個(gè)結(jié)點(diǎn)

題目描述

給定一個(gè)二叉樹和其中的一個(gè)結(jié)點(diǎn)，請找出中序遍歷順序的下一個(gè)結(jié)點(diǎn)并且返回愕难。注意早龟，樹中的結(jié)點(diǎn)不僅包含左右子結(jié)點(diǎn)，同時(shí)包含指向父結(jié)點(diǎn)的指針猫缭。

解題思路

畫圖葱弟，可知各種情況的下一個(gè)結(jié)點(diǎn)。

如果pNode為空猜丹，則返回null芝加。
如果pNode不為空，判斷pNode是否有右子樹射窒，如果有右子樹藏杖，則返回右子樹中最左邊的結(jié)點(diǎn)将塑。如果沒有右子樹，則向上找pNode的父結(jié)點(diǎn)蝌麸。
如果沒有父結(jié)點(diǎn)点寥，則pNode是根節(jié)點(diǎn)，中序遍歷已經(jīng)遍歷完祥楣，返回null开财；如果有父結(jié)點(diǎn)，且如果它是父結(jié)點(diǎn)的左結(jié)點(diǎn)误褪，直接返回pNode的父結(jié)點(diǎn)；如果有父結(jié)點(diǎn)碾褂，且如果它是父結(jié)點(diǎn)的右結(jié)點(diǎn)兽间，則要看pNode的祖父結(jié)點(diǎn)。
如果沒有祖父結(jié)點(diǎn)正塌，則中序遍歷已經(jīng)遍歷完嘀略，返回null；如果pNode的父結(jié)點(diǎn)是祖父結(jié)點(diǎn)的左結(jié)點(diǎn)乓诽，則返回祖父結(jié)點(diǎn)帜羊；如果有父結(jié)點(diǎn)，且如果pNode的父結(jié)點(diǎn)是祖父結(jié)點(diǎn)的右結(jié)點(diǎn)鸠天，則中序遍歷已經(jīng)遍歷完讼育，返回null。

public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode){
        if(pNode == null){return null;}//如果結(jié)點(diǎn)為空稠集，則返回null
        if(pNode.right!=null){//如果結(jié)點(diǎn)有右子樹奶段，則找到子樹的最左的結(jié)點(diǎn)
            pNode = pNode.right;
            while(pNode.left!=null){//找到最左的結(jié)點(diǎn)
                pNode = pNode.left;
            }
            return pNode;
        }else{//如果改結(jié)點(diǎn)沒有右子樹，就只能往上找其父結(jié)點(diǎn)
            if(pNode.next!=null && pNode.next.left==pNode){//有父結(jié)點(diǎn)剥纷，且是父結(jié)點(diǎn)的左結(jié)點(diǎn)痹籍，則直接返回pNode的父結(jié)點(diǎn)
                return pNode.next;
            }else if(pNode.next!=null && pNode.next.right==pNode){//有父結(jié)點(diǎn)，且是父極點(diǎn)的右結(jié)點(diǎn)
                if(pNode.next.next!=null && pNode.next.next.left==pNode.next){
                //如果祖父結(jié)點(diǎn)存在晦鞋，且其父結(jié)點(diǎn)是祖父結(jié)點(diǎn)的左結(jié)點(diǎn)蹲缠，則返回其祖父結(jié)點(diǎn)
                    return pNode.next.next;
                }else if(pNode.next.next!=null && pNode.next.next.right==pNode.next){
                //如果祖父結(jié)點(diǎn)存在，且其父結(jié)點(diǎn)是祖父結(jié)點(diǎn)的右結(jié)點(diǎn)悠垛，則返回null线定，中序遍歷后面沒有結(jié)點(diǎn)了
                    return null;
                }else{//如果祖父結(jié)點(diǎn)不存在，也就是其父結(jié)點(diǎn)就是根結(jié)點(diǎn)鼎文，中序遍歷后面已經(jīng)沒有結(jié)點(diǎn)了渔肩，返回null
                    return null;
                }
            }else{//如果他沒有父結(jié)點(diǎn)，則它是根節(jié)點(diǎn)
                return null;//這種情況就是根節(jié)點(diǎn)只有左子樹拇惋，右邊全為空周偎，根節(jié)點(diǎn)就是最后一個(gè)結(jié)點(diǎn)，返回null
            }
        }
    }
}

58蓉坎、對稱的二叉樹

題目描述

請實(shí)現(xiàn)一個(gè)函數(shù)，用來判斷一顆二叉樹是不是對稱的蛉艾。注意钳踊，如果一個(gè)二叉樹同此二叉樹的鏡像是同樣的，定義其為對稱的勿侯。

解題思路

根節(jié)點(diǎn)只有一個(gè)拓瞪，不用管其對稱性，拋開根節(jié)點(diǎn)助琐，看根節(jié)點(diǎn)的左右子樹祭埂。
如果左右兩顆子樹是鏡像的，則這兩顆子樹的根節(jié)點(diǎn)的值是一樣的兵钮，且其left.left與right.right是鏡像的蛆橡；其left.right與right.left是鏡像的。

public class Solution {
    boolean isSymmetrical(TreeNode pRoot){
        if(pRoot==null){return true;}//如果根節(jié)點(diǎn)為空掘譬，則返回true
        return isSym(pRoot.left, pRoot.right);//看根節(jié)點(diǎn)的左右子樹是否是鏡像的
    }
    boolean isSym(TreeNode left, TreeNode right){
        if(left==null && right==null){return true;}//如果兩顆樹都為空泰演，則返回true
        if(left!=null && right==null){return false;}//如果左不空，右空葱轩，則不是鏡像的
        if(left==null && right!=null){return false;}//如果左空睦焕，右不空，則不是鏡像的
        if(left.val != right.val){return false;}//如果左右都不空酿箭，但是左右子樹的根節(jié)點(diǎn)的值不一樣复亏，則不是鏡像的
        //左右都不空，則查看left.left與right.right是否鏡像缭嫡，其left.right與right.left是否鏡像
        return isSym(left.left, right.right) && isSym(left.right, right.left);
    }
}

59缔御、按之字形打印二叉樹

題目描述

請實(shí)現(xiàn)一個(gè)函數(shù)按照之字形打印二叉樹，即第一行按照從左到右的順序打印妇蛀，第二層按照從右至左的順序打印耕突，第三行按照從左到右的順序打印，其他行以此類推评架。

解題思路

設(shè)置一個(gè)boolean left2right來判斷是應(yīng)該從左往右還是從右往左眷茁。
有一種方法是用兩個(gè)棧，一個(gè)是奇數(shù)層棧纵诞，一個(gè)是偶數(shù)層棧上祈。可參考牛客網(wǎng)登刺。
層次遍歷一棵樹容易想到用隊(duì)列籽腕，可以簡單地在將結(jié)點(diǎn)的value插到list的最前面，但是這種方法肯定不能用于海量數(shù)據(jù)纸俭。java中的LinkedList可以用來實(shí)現(xiàn)隊(duì)列皇耗，這個(gè)隊(duì)列的實(shí)現(xiàn)是雙向鏈表，是可以正向迭代和反向迭代的揍很。

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Iterator;

public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> final_list = new ArrayList<>();
        if(pRoot==null){return final_list;}
        boolean left2right = true;
        ArrayList<Integer> list = new ArrayList<>();
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(null);//分隔符在一層結(jié)點(diǎn)的前面比較方便
        queue.offer(pRoot);
        while(queue.size()!=1){//到最后只剩下一個(gè)null的時(shí)候結(jié)束循環(huán)
            TreeNode node = queue.poll();//隊(duì)頭結(jié)點(diǎn)出隊(duì)列
            if(node == null){//遇到分界符號
                Iterator<TreeNode> iter = null;//對隊(duì)列中的結(jié)點(diǎn)進(jìn)行迭代郎楼，但不出隊(duì)列
                if(left2right){
                    iter = queue.iterator();//正向迭代器
                }else{
                    iter = queue.descendingIterator();//反向迭代器
                }
                left2right = !left2right;//將迭代方向反向
                while(iter.hasNext()){
                    TreeNode temp = (TreeNode)iter.next();//迭代隊(duì)中的每個(gè)元素，加入list
                    list.add(temp.val);
                }//一般遍歷樹時(shí)我們將結(jié)點(diǎn)出隊(duì)窒悔，并將val加入list呜袁，但是這里只對隊(duì)中的元素迭代，并不出隊(duì)简珠。另外傅寡，此時(shí)遍歷時(shí)，隊(duì)中只有結(jié)點(diǎn)北救，沒有null
                final_list.add(new ArrayList<Integer>(list));//拷貝一個(gè)list加入final_list
                list.clear();//清空list
                queue.offer(null);//隊(duì)中元素迭代完了之后加入null
            }else{
                if(node.left!=null){queue.offer(node.left);}//我們將元素迭代完了之后再將元素遍歷一遍，此時(shí)只需要將這里元素的左右結(jié)點(diǎn)加入隊(duì)即可
                if(node.right!=null){queue.offer(node.right);}
            }
        }
        return final_list;
    }
}

60芜抒、把二叉樹打印成多行

題目描述

從上到下按層打印二叉樹珍策，同一層結(jié)點(diǎn)從左至右輸出。每一層輸出一行宅倒。

解題思路

層次遍歷很容易想到用隊(duì)列攘宙。牛客評論區(qū)還有利用遞歸方法的拐迁，遞歸是深度優(yōu)先蹭劈，但是他通過對方法傳入深度值來指定將結(jié)點(diǎn)加入哪一個(gè)list，從而使返回結(jié)果看起來像層次遍歷线召。
隊(duì)列版本：

import java.util.ArrayList;
import java.util.LinkedList;

public class Solution {
    ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> final_list = new ArrayList<>();
        if(pRoot==null){return final_list;}
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(pRoot);
        queue.offer(null);//分界符號
        final_list.add(new ArrayList<Integer>());//新建一個(gè)list加入fianl_list
        while(queue.size()!=1){//如果隊(duì)列只剩下一個(gè)元素铺韧，則這個(gè)元素一定是分界符號
            TreeNode node = queue.poll();//取隊(duì)頭元素
            if(node!=null){//如果隊(duì)頭不是分界符號
                final_list.get(final_list.size()-1).add(node.val);//將val加入相應(yīng)list
                if(node.left!=null){queue.offer(node.left);}//如果左子樹非空，則將左子樹的根節(jié)點(diǎn)加入隊(duì)列
                if(node.right!=null){queue.offer(node.right);}//如果右子樹非空缓淹，則將右子樹的根節(jié)點(diǎn)加入隊(duì)列
            }else{//如果遇到了分界符號哈打，則分界符號前面的層已經(jīng)遍歷完
                final_list.add(new ArrayList<Integer>());//新建一個(gè)list，為下一層的遍歷做準(zhǔn)備
                queue.offer(null);//下一層已經(jīng)全部入隊(duì)列讯壶，最后加入分界符號
            }
        }
        return final_list;
    }
}

遞歸版本：

import java.util.ArrayList;

public class Solution {
    ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> final_list = new ArrayList<>();
        if(pRoot==null){return final_list;}
        return depth(pRoot, 1, final_list);
    }
    ArrayList<ArrayList<Integer>> depth(TreeNode p, int depth, ArrayList<ArrayList<Integer>> final_list){
        if(depth > final_list.size()){//當(dāng)前要遍歷新層
            final_list.add(new ArrayList<Integer>());//建一個(gè)新層對應(yīng)的list加入final_list
            final_list.get(depth-1).add(p.val);//將當(dāng)前結(jié)點(diǎn)加入對應(yīng)的list
        }else{//當(dāng)前層對應(yīng)的list已經(jīng)建立料仗，則將當(dāng)前結(jié)點(diǎn)的val加入對應(yīng)list
            final_list.get(depth-1).add(p.val);
        }
        if(p.left!=null){depth(p.left, depth+1, final_list);}//左不為空則遞歸左
        if(p.right!=null){depth(p.right, depth+1, final_list);}//右不為空則遞歸右
        return final_list;
    }
}

結(jié)尾

如果您發(fā)現(xiàn)我的文章有任何錯(cuò)誤，或?qū)ξ业奈恼掠惺裁春玫慕ㄗh伏蚊，請聯(lián)系我立轧！如果您喜歡我的文章，請點(diǎn)喜歡~*我是藍(lán)白絳，感謝你的閱讀氛改！

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末帐萎，一起剝皮案震驚了整個(gè)濱河市，隨后出現(xiàn)的幾起案子平窘，更是在濱河造成了極大的恐慌吓肋，老刑警劉巖，帶你破解...
沈念sama閱讀 211,194評論 6贊 490
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件瑰艘，死亡現(xiàn)場離奇詭異是鬼，居然都是意外死亡，警方通過查閱死者的電腦和手機(jī)紫新，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 90,058評論 2贊 385
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門均蜜，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人芒率，你說我怎么就攤上這事囤耳。” “怎么了偶芍？”我有些...
開封第一講書人閱讀 156,780評論 0贊 346
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵充择，是天一觀的道長。經(jīng)常有香客問我匪蟀，道長椎麦，這世上最難降的妖魔是什么？我笑而不...
開封第一講書人閱讀 56,388評論 1贊 283
?港島之戀（遺憾婚禮）
正文為了忘掉前任材彪，我火速辦了婚禮观挎，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘段化。我一直安慰自己嘁捷，他們只是感情好，可當(dāng)我...
茶點(diǎn)故事閱讀 65,430評論 5贊 384
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布显熏。她就那樣靜靜地躺著雄嚣，像睡著了一般。火紅的嫁衣襯著肌膚如雪佃延。梳的紋絲不亂的頭發(fā)上现诀，一...
開封第一講書人閱讀 49,764評論 1贊 290
城市分裂傳說
那天，我揣著相機(jī)與錄音履肃，去河邊找鬼仔沿。笑死，一個(gè)胖子當(dāng)著我的面吹牛尺棋，可吹牛的內(nèi)容都是我干的封锉。我是一名探鬼主播绵跷，決...
沈念sama閱讀 38,907評論 3贊 406
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼，長吁一口氣：“原來是場噩夢啊……” “哼成福！你這毒婦竟也來了碾局？” 一聲冷哼從身側(cè)響起，我...
開封第一講書人閱讀 37,679評論 0贊 266
萬榮殺人案實(shí)錄
序言：老撾萬榮一對情侶失蹤奴艾，失蹤者是張志新（化名）和其女友劉穎净当，沒想到半個(gè)月后，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體蕴潦，經(jīng)...
沈念sama閱讀 44,122評論 1贊 303
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡像啼，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 36,459評論 2贊 325
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了潭苞。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片忽冻。...
茶點(diǎn)故事閱讀 38,605評論 1贊 340
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡，死狀恐怖此疹，靈堂內(nèi)的尸體忽然破棺而出僧诚，到底是詐尸還是另有隱情，我是刑警寧澤蝗碎，帶...
沈念sama閱讀 34,270評論 4贊 329
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布湖笨，位于F島的核電站，受9級特大地震影響蹦骑，放射性物質(zhì)發(fā)生泄漏赶么。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 39,867評論 3贊 312
男人毒藥：我在死后第九天來索命
文/蒙蒙一脊串、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧清钥，春花似錦琼锋、人聲如沸。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,734評論 0贊 21
一樁弒父案缕坎，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽。三九已至篡悟，卻和暖如春谜叹，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背搬葬。一陣腳步聲響...
開封第一講書人閱讀 31,961評論 1贊 265
情欲美人皮
我被黑心中介騙來泰國打工荷腊，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人急凰。一個(gè)月前我還...
沈念sama閱讀 46,297評論 2贊 360
代替公主和親
正文我出身青樓女仰，卻偏偏與公主長得像，于是被迫代替她去往敵國和親。傳聞我的和親對象是個(gè)殘疾皇子疾忍，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 43,472評論 2贊 348

劍指offer｜51-60題解題思路及代碼(Java版)

劍指offer51到60題總覽：

51功戚、構(gòu)建乘積數(shù)組

題目描述

解題思路

52属桦、正則表達(dá)式匹配

題目描述

解題思路

53、表示數(shù)值的字符串

題目描述

解題思路

54、字符流中第一個(gè)不重復(fù)的字符

題目描述

55睦尽、鏈表中環(huán)的入口結(jié)點(diǎn)

題目描述

解題思路

56芬探、刪除鏈表中重復(fù)的結(jié)點(diǎn)

題目描述

解題思路

57挫酿、二叉樹的下一個(gè)結(jié)點(diǎn)

題目描述

解題思路

58蓉坎、對稱的二叉樹

題目描述

解題思路

59缔御、按之字形打印二叉樹

題目描述

解題思路

60芜抒、把二叉樹打印成多行

題目描述

解題思路

結(jié)尾

推薦閱讀更多精彩內(nèi)容