Java LeetCode篇-深入了解二叉樹經(jīng)典解法（三種方式實(shí)現(xiàn)：獲取二叉樹的最大深度）

這篇具有很好參考價(jià)值的文章主要介紹了Java LeetCode篇-深入了解二叉樹經(jīng)典解法（三種方式實(shí)現(xiàn)：獲取二叉樹的最大深度）。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問。

??博客主頁：?【小扳_-CSDN博客】
?感謝大家點(diǎn)贊??收藏?評(píng)論???

Java LeetCode篇-深入了解二叉樹經(jīng)典解法（三種方式實(shí)現(xiàn)：獲取二叉樹的最大深度）,Java LeetCode篇,leetcode,算法,職場(chǎng)和發(fā)展,java,鏈表

文章目錄

? ? ? ? 1.0 對(duì)稱二叉樹

????????1.1 判斷對(duì)稱二叉樹實(shí)現(xiàn)思路

????????1.2 代碼實(shí)現(xiàn)：判斷對(duì)稱二叉樹

? ? ? ? 2.0 二叉樹的最大深度

????????2.1 使用遞歸實(shí)現(xiàn)獲取二叉樹的最大深度思路

? ? ? ? 2.2 代碼實(shí)現(xiàn)：使用遞歸實(shí)現(xiàn)獲取二叉樹的最大深度

? ? ? ? 2.3 使用非遞歸實(shí)現(xiàn)獲取二叉樹的最大深度思路

? ? ? ? 2.4 代碼實(shí)現(xiàn)：使用非遞歸實(shí)現(xiàn)獲取二叉樹的最大深度

? ? ? ? 2.5 使用層序遍歷實(shí)現(xiàn)獲取二叉樹的最大深度

? ? ? ? 2.6 代碼實(shí)現(xiàn)：使用層序遍歷實(shí)現(xiàn)獲取二叉樹的最大深度

? ? ? ? 3.0 二叉樹的最小深度

? ? ? ? 3.1?使用遞歸實(shí)現(xiàn)獲取二叉樹的最小深度思路

? ? ? ? 3.2?代碼實(shí)現(xiàn)：使用遞歸實(shí)現(xiàn)獲取二叉樹最小深度

? ? ? ? 3.3?使用層序遍歷實(shí)現(xiàn)獲取二叉樹的最小深度思路

? ? ? ? 3.4?代碼實(shí)現(xiàn)：使用層序遍歷實(shí)現(xiàn)獲取二叉樹的最小深度

? ? ? ? 4.0 翻轉(zhuǎn)二叉樹

? ? ? ? 4.1 使用實(shí)現(xiàn)遞歸翻轉(zhuǎn)二叉樹思路

? ? ? ? 4.2 代碼實(shí)現(xiàn)：使用遞歸翻轉(zhuǎn)二叉樹

? ? ? ? 5.0 二叉樹經(jīng)典解法的完整代碼

? ? ? ? 1.0 對(duì)稱二叉樹

題目：

????????給你一個(gè)二叉樹的根節(jié)點(diǎn)?root?，檢查它是否軸對(duì)稱。

示例 1：
輸入：root = [1,2,2,3,4,4,3]
輸出：true
示例 2：
輸入：root = [1,2,2,null,3,null,3]
輸出：false
OJ鏈接：

101.?對(duì)稱二叉樹

? ? ? ? 1.1 判斷對(duì)稱二叉樹實(shí)現(xiàn)思路

? ? ?假設(shè)該樹的圖：? ?

? ? ? ? 具體思路為：如果當(dāng)前節(jié)點(diǎn)的左子樹的值等于當(dāng)前節(jié)點(diǎn)的右子樹時(shí)，可以說目前為止還是對(duì)稱的，不能直接下結(jié)論，因?yàn)椴荒鼙ＷC之后的節(jié)點(diǎn)是否對(duì)稱。比如：當(dāng)前節(jié)點(diǎn)的值為 1 ，它的左孩子的值為 2 ，它的右孩子的值為 2，此時(shí)可以說暫時(shí)是對(duì)稱的，還需要接著向下判斷。它的左孩子的左孩子的值為 3，它的右孩子的右孩子為 3 ，同理，現(xiàn)在還不能說明該樹是否對(duì)稱，當(dāng)遞歸到底的時(shí)候，當(dāng)前的節(jié)點(diǎn)的左右孩子都是 null ，此時(shí)可以返回 true ，不能足以證明該樹對(duì)稱，因?yàn)閱螁沃皇桥袛嗤晖鈧?cè)的節(jié)點(diǎn)，在外層回歸的過程中，需要判斷內(nèi)層的節(jié)點(diǎn)是否對(duì)稱，回歸到節(jié)點(diǎn)值都為 2 的節(jié)點(diǎn)，接著進(jìn)行內(nèi)層遞歸，對(duì)于在外層判斷完左孩子，那么接下來需要判斷右孩子，同樣，對(duì)于在外層判斷完右孩子，那么接下來需要判斷左孩子。如，剛剛的外層結(jié)束遞出之后，開始回歸，到節(jié)點(diǎn)為 2 的節(jié)點(diǎn)，對(duì)于左邊的節(jié)點(diǎn)值為 2 的節(jié)點(diǎn)的右孩子，與右邊的節(jié)點(diǎn)值為 2 的節(jié)點(diǎn)的左孩子進(jìn)行比較，如果相同，由于說明不了什么，還得繼續(xù)往下遞出，直到該節(jié)點(diǎn)的左右孩子都為 null 時(shí)，可以返回 true 。最后返回到節(jié)點(diǎn)值為 1 的根節(jié)點(diǎn)中，可以得到該樹是對(duì)稱。

? ? ? ? 在無論是外層遞出還是內(nèi)層遞出：

? ? ? ? ?- 當(dāng)左右孩子節(jié)點(diǎn)的值不相同的時(shí)候，就說明了該樹時(shí)不相等的，直接返回 false ；

? ? ? ? ?- 遇到一個(gè)節(jié)點(diǎn)的左孩子不為 null 而右孩子為 null 時(shí)，可以直接返回 false ，不需要接著往后遞出了。同理，遇到一個(gè)節(jié)點(diǎn)的右孩子不為 null ，而左孩子為 null 時(shí)，直接返回 false ；

? ? ? ? ?- 當(dāng)且僅當(dāng)，當(dāng)該節(jié)點(diǎn)的左右孩子都為 null 時(shí)，返回 true ；

? ? ? ? 1.2 代碼實(shí)現(xiàn)：判斷對(duì)稱二叉樹

    //判斷對(duì)稱二叉樹
    public boolean isSymmetry(TreeNode root) {
        return isSymmetryRecursion(root.left,root.right);
    }

    private boolean isSymmetryRecursion(TreeNode left,TreeNode right) {
        if (left == null && right == null ) {
            return true;
        }
        if (left == null || right == null) {
            return false;
        }
        if (left.val != right.val) {
            return false;
        }
        return isSymmetryRecursion(left.left,right.right) && isSymmetryRecursion(left.right,right.left);

    }

? ? ? ? 大體上的思路跟后序遍歷二叉樹一致。

? ? ? ? 2.0 二叉樹的最大深度

題目：

????????給定一個(gè)二叉樹?root?，返回其最大深度。

二叉樹的?最大深度?是指從根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長(zhǎng)路徑上的節(jié)點(diǎn)數(shù)。

示例 1：
輸入：root = [3,9,20,null,null,15,7]
輸出：3
OJ鏈接：

104.?二叉樹的最大深度

? ? ? ? ?2.1 使用遞歸實(shí)現(xiàn)獲取二叉樹的最大深度思路

????????具體思路為：先從整體思路出發(fā)，得到最大的深度，無非就是比較左右子樹的深度，選取較大的值 + 1，返回即可。當(dāng)遇到的節(jié)點(diǎn)為 null 時(shí)，返回 0 ，結(jié)束遞出。比如，節(jié)點(diǎn)值為 3 的節(jié)點(diǎn)，它的左子樹的深度為 1，它的右子樹的深度為 2 ,那么選取最大的值為 2 ，最后最大的值再加上 1 ，所以得出的該樹的最大深度為 3 。

? ? ? ? 接下來具體分析每一個(gè)節(jié)點(diǎn)：根節(jié)點(diǎn)值為 3 ，先獲取左子樹的深度：沿著該方向遞出，直到遇到當(dāng)前節(jié)點(diǎn)的左右孩子都為 null 時(shí)，返回 0 ，所以值為 9 的節(jié)點(diǎn)目前返回上一個(gè)遞歸調(diào)用的值為 1 ，對(duì)于根節(jié)點(diǎn)的左子樹的深度為 1?；再獲取右子樹的深度：沿著根節(jié)點(diǎn)的右子樹遞出，這次遇到的節(jié)點(diǎn)的左右子樹都不為 null 時(shí)，對(duì)于當(dāng)前值為 20 的節(jié)點(diǎn)來說，需要獲取該左右子樹的最大的值，先獲取左子樹的深度：沿著該方式遞出，直到遇到的節(jié)點(diǎn)為 null 時(shí)，返回 0，節(jié)點(diǎn)值為 15 的節(jié)點(diǎn)的左右孩子都為 null ，返回 0 + 1 ，所以對(duì)于節(jié)點(diǎn) 20 來說，該左子樹的深度為 1 ；接著繼續(xù)來獲取節(jié)點(diǎn)值為 20 的右子樹的深度：沿著該方式遞出，直到遇到的節(jié)點(diǎn)為 null 時(shí)，返回 0，節(jié)點(diǎn)值為 7 的左右孩子都為 null ，返回 0 + 1。那么選取較大的值 + 1，就是節(jié)點(diǎn)值為 20 的深度為 2 。相對(duì)與根節(jié)點(diǎn)來說已經(jīng)得到了左右子樹的深度了，分別為 1 與 2 ，選取最大的值 2 再加 1 就是該樹的最大深度為 3 。

? ? ? ? 2.2 代碼實(shí)現(xiàn)：使用遞歸實(shí)現(xiàn)獲取二叉樹的最大深度

    //用遞歸方式求樹的最大深度
    public int maximumDepthRecursion(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int l = maximumDepth(node.left);
        int r = maximumDepth(node.right);
        return Math.max(l,r) + 1;

    }

? ? ? ? 大體上思路跟后序遍歷思路大致相同。

? ? ? ? 2.3 使用非遞歸實(shí)現(xiàn)獲取二叉樹的最大深度思路

? ? ? ? 具體思路為：在之前講到使用非遞歸實(shí)現(xiàn)后序遍歷的思路，跟這里的思路大致一致。簡(jiǎn)單再講一下思路，根節(jié)點(diǎn)從左孩子開始出發(fā)，在到下一個(gè)節(jié)點(diǎn)之前，需要先把該節(jié)點(diǎn)壓入棧中，直到 node == null 時(shí)，不再繼續(xù)下去，按照原路返回。由于需要完成對(duì)右節(jié)點(diǎn)的操作后，需要返回該節(jié)點(diǎn)，所以不能直接把棧頂元素彈出，先查找棧頂元素，查看該右孩子是否為 null 或者已經(jīng)完成對(duì)右孩子的相關(guān)操作之后，這才能彈出棧頂元素。如果以上情況都不符合，需要對(duì)右孩子進(jìn)行處理。以上就是使用非遞歸實(shí)現(xiàn)后序循環(huán)，那么結(jié)合該題求樹的最大深度，即什么時(shí)候棧的元素達(dá)到最大的時(shí)候，這時(shí)候就是樹的最大深度。

? ? ? ? 2.4 代碼實(shí)現(xiàn)：使用非遞歸實(shí)現(xiàn)獲取二叉樹的最大深度

    //用非遞歸方式求樹的最大深度
    public int maximumDepth(TreeNode root) {
        TreeNode curr = root;
        LinkedList<TreeNode> stack = new LinkedList<>();
        int max = 0;
        TreeNode pop = null;
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                stack.push(curr);
                curr = curr.left;
                if (max < stack.size()) {
                    max = stack.size();
                }
            } else {
                TreeNode peek = stack.peek();
                if ( peek.right == null || peek.right == pop ) {
                    pop = stack.pop();
                }else {
                    curr = peek.right;
                }
            }
        }
        return max;
    }

? ? ? ? 當(dāng)然，這個(gè)時(shí)間復(fù)雜度比使用遞歸實(shí)現(xiàn)的要大，效率不如使用遞歸的實(shí)現(xiàn)二叉樹最大深度。

? ? ? ? 2.5 使用層序遍歷實(shí)現(xiàn)獲取二叉樹的最大深度

? ? ? ? 先了解層序遍歷：顧名思義，按照層級(jí)進(jìn)行依次訪問節(jié)點(diǎn)。將每個(gè)節(jié)點(diǎn)壓入隊(duì)列中，按照先進(jìn)先出的順序依次訪問隊(duì)列中的節(jié)點(diǎn)。具體來說，我們從根節(jié)點(diǎn)開始，將根節(jié)點(diǎn)壓入隊(duì)列中，然后依次從隊(duì)列中取出節(jié)點(diǎn)，將其左右子節(jié)點(diǎn)（如果存在）壓入隊(duì)列中。

????????需要準(zhǔn)備隊(duì)列來存儲(chǔ)節(jié)點(diǎn)，根據(jù)該數(shù)據(jù)結(jié)構(gòu)的特性：先進(jìn)先出，一開始先讓根節(jié)點(diǎn)壓入隊(duì)列中，接著從隊(duì)列中彈出來，如果彈出來的節(jié)點(diǎn)的左孩子不為 null 時(shí)，將其壓入隊(duì)列中；如果左孩子為 null 時(shí)，不需要壓入隊(duì)列中；同理，如果彈出來節(jié)點(diǎn)的右孩子不為 null 時(shí)，將其壓入隊(duì)列中。循環(huán)結(jié)束條件為：當(dāng)隊(duì)列中的元素個(gè)數(shù)為 0 時(shí)，退出循環(huán)。

? ? ? ? 再結(jié)合該題的邏輯，該二叉樹的最大深度就是樹的層級(jí)數(shù)量。那么怎么才能得出 int depth 層級(jí)數(shù)量呢？再嵌套一個(gè)內(nèi)層循環(huán)，每一層遍歷結(jié)束之后，depth++ 。內(nèi)層循環(huán)的次數(shù)為：當(dāng)前的隊(duì)列的元素的個(gè)數(shù)。

? ? ? ? 2.6 代碼實(shí)現(xiàn)：使用層序遍歷實(shí)現(xiàn)獲取二叉樹的最大深度

    //使用層序遍歷求樹的最大深度
    public int sequenceMaxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        int depth = 0;
        while ( !queue.isEmpty()) {
            int size = queue.size();
            for (int j = 0; j < size; j++) {
                TreeNode tp = queue.poll();
                if (tp.left != null) {
                    queue.offer(tp.left);
                }
                if (tp.right != null) {
                    queue.offer(tp.right);
                }
                //System.out.print(tp.val + " ");
            }
            //System.out.println();
            depth++;
        }
        return depth;
    }

? ? ? ? 3.0 二叉樹的最小深度

題目：

????????給定一個(gè)二叉樹，找出其最小深度。

最小深度是從根節(jié)點(diǎn)到最近葉子節(jié)點(diǎn)的最短路徑上的節(jié)點(diǎn)數(shù)量。

說明：葉子節(jié)點(diǎn)是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)。

示例 1：
輸入：root = [3,9,20,null,null,15,7]
輸出：2
OJ鏈接：

111.?二叉樹的最小深度

????????二叉樹的最小深度是指從根節(jié)點(diǎn)到最近葉子節(jié)點(diǎn)的最短路徑上的節(jié)點(diǎn)數(shù)量。換句話說，最小深度是從根節(jié)點(diǎn)到最近的葉子節(jié)點(diǎn)的路徑長(zhǎng)度。

? ? ? ? 3.1?使用遞歸實(shí)現(xiàn)獲取二叉樹的最小深度思路

? ? ? ? 具體思路為：思路大體跟或去最大深度的思路差不太多，當(dāng)比較前節(jié)點(diǎn)的左右子樹，獲取最小的值 + 1 ，則為當(dāng)前節(jié)點(diǎn)的深度。獲取最小深度相較于獲取最大深度，多了一個(gè)判斷條件，如果當(dāng)前節(jié)點(diǎn)為 0 時(shí)，不應(yīng)該參與比較。

如圖例，該樹的深度應(yīng)該為 2 ，如果不加額外的條件來判斷左右孩子節(jié)點(diǎn)是否為 null 時(shí)，那么此時(shí)根節(jié)點(diǎn)的右孩子為 null ，所以右子樹為深度為 0?；左孩子不為 null ，接著遞歸下去，直到 node == null 為止，從圖可知，該根節(jié)點(diǎn)的左子樹的深度為 1，因此用 1 與 0 來比較，獲取最小的值為 0 ，再加上 1 ,最后結(jié)果為 1 。很明顯不符合要求。所以，一定要加條件來判斷，查看該節(jié)點(diǎn)的左右孩子是否為 null ，如果為 null ，需要返回另一個(gè)節(jié)點(diǎn) + 1 當(dāng)作當(dāng)前節(jié)點(diǎn)的深度。

? ? ? ? 3.2?代碼實(shí)現(xiàn)：使用遞歸實(shí)現(xiàn)獲取二叉樹最小深度

    //使用遞歸求樹的最小深度
    public int minDepth(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int l = minDepth(node.left);
        int r = minDepth(node.right);
        if (l == 0) {
            return r + 1;
        }
        if (r == 0) {
            return l + 1;
        }

        return Math.min(l,r) + 1;

    }

? ? ? ? 3.3?使用層序遍歷實(shí)現(xiàn)獲取二叉樹的最小深度思路

? ? ? ? 具體思路為：當(dāng)帶一個(gè)遇到的葉子節(jié)點(diǎn)時(shí)，當(dāng)前的層數(shù)就是該樹的最小深度。

? ? ? ? 3.4?代碼實(shí)現(xiàn)：使用層序遍歷實(shí)現(xiàn)獲取二叉樹的最小深度

    //使用層序遍歷求得樹的最小深度
    public int sequenceMinDepth(TreeNode root) {
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        while (!queue.isEmpty()) {
            depth++;
            int size = queue.size();
            for (int i = 0; i < size ; i++) {
                TreeNode poll = queue.poll();
                if (poll.right == null && poll.left == null) {
                    return depth;
                }
                if (poll.left != null) {
                    queue.offer(poll.left);
                }
                if (poll.right != null) {
                    queue.offer(poll.right);
                }
            }
        }
        return depth;
    }

????????

? ? ? ? 4.0 翻轉(zhuǎn)二叉樹

題目：

????????給定一棵二叉樹的根節(jié)點(diǎn)?root，請(qǐng)左右翻轉(zhuǎn)這棵二叉樹，并返回其根節(jié)點(diǎn)。

示例 1：
輸入：root = [5,7,9,8,3,2,4]
輸出：[5,9,7,4,2,3,8]
OJ鏈接：

LCR 144.?翻轉(zhuǎn)二叉樹

? ? ? ? 4.1 使用實(shí)現(xiàn)遞歸翻轉(zhuǎn)二叉樹思路

? ? ? ? 具體思路為：從整體來看，將當(dāng)前節(jié)點(diǎn)的左右節(jié)點(diǎn)進(jìn)行翻轉(zhuǎn)，每一個(gè)節(jié)點(diǎn)都是如此，遞歸結(jié)束條件為 node == null 時(shí)，結(jié)束遞出?；貧w到每一個(gè)節(jié)點(diǎn)的右子樹進(jìn)行翻轉(zhuǎn)。

? ? ? ? 4.2 代碼實(shí)現(xiàn)：使用遞歸翻轉(zhuǎn)二叉樹

    //翻轉(zhuǎn)二叉樹
    public void rollbackRecursion(TreeNode node) {
        if (node == null) {
            return;
        }
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;

        rollbackRecursion(node.left);
        rollbackRecursion(node.right);
    }

? ? ? ? 5.0 二叉樹經(jīng)典解法的完整代碼

回顧本章代碼，進(jìn)一步鞏固：

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

public class TreeNode {

    private TreeNode left;
    private int val;
    private TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(TreeNode left, int val, TreeNode right) {
        this.left = left;
        this.val = val;
        this.right = right;
    }

    //遞歸實(shí)現(xiàn)前序遍歷
    public void prevRecursion(TreeNode node) {
        if (node == null) {
            return;
        }
        System.out.print(node.val + " ");
        prevRecursion(node.left);
        prevRecursion(node.right);
    }


    //遞歸實(shí)現(xiàn)中序遍歷
    public void midRecursion(TreeNode node) {
        if (node == null) {
            return;
        }
        midRecursion(node.left);
        System.out.print(node.val + " ");
        midRecursion(node.right);
    }


    //遞歸實(shí)現(xiàn)后序遍歷
    public void postRecursion(TreeNode node) {

        if (node == null) {
            return;
        }
        postRecursion(node.left);
        postRecursion(node.right);
        System.out.print(node.val + " ");
    }

    //非遞歸實(shí)現(xiàn)前序遍歷
    public List<Integer> prev(TreeNode root) {
        TreeNode node = root;
        LinkedList<TreeNode> stack = new LinkedList<>();
        List<Integer> list = new ArrayList<>();
        while (node != null || !stack.isEmpty()) {
            if (node != null) {
                stack.push(node);
                list.add(node.val);
                node = node.left;
            }else {
                TreeNode tp = stack.pop();
                node = tp.right;
            }
        }
        return list;
    }

    //非遞歸實(shí)現(xiàn)中序遍歷
    public void mid(TreeNode root) {
        TreeNode node = root;
        LinkedList<TreeNode> stack = new LinkedList<>();

        while (node != null || !stack.isEmpty()) {
            if (node != null) {
                stack.push(node);

                node = node.left;
            }else {
                TreeNode tp = stack.pop();
                System.out.print(tp.val + " ");
                node = tp.right;
            }
        }
        System.out.println();

    }

    //非遞歸實(shí)現(xiàn)后序遍歷
    public List<Integer> post(TreeNode root) {
        TreeNode node = root;
        TreeNode pop = null;
        List<Integer> list = new ArrayList<>();
        LinkedList<TreeNode> stack = new LinkedList<>();
        while ( node != null || !stack.isEmpty()) {
            if (node != null) {
                stack.push(node);
                node = node.left;
            }else {
                TreeNode tp = stack.peek();
                if (tp.right == null || tp.right == pop) {
                    pop = stack.pop();
                    list.add(pop.val);
                }else {
                    node = tp.right;
                }
            }
        }
        return list;
    }

    //判斷對(duì)稱二叉樹
    public boolean isSymmetry(TreeNode root) {
        return isSymmetryRecursion(root.left,root.right);
    }

    private boolean isSymmetryRecursion(TreeNode left,TreeNode right) {
        if (left == null && right == null ) {
            return true;
        }
        if (left == null || right == null) {
            return false;
        }
        if (left.val != right.val) {
            return false;
        }
        return isSymmetryRecursion(left.left,right.right) && isSymmetryRecursion(left.right,right.left);

    }

    //用遞歸方式求樹的最大深度
    public int maximumDepthRecursion(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int l = maximumDepth(node.left);
        int r = maximumDepth(node.right);
        return Math.max(l,r) + 1;

    }

    //用非遞歸方式求樹的最大深度
    public int maximumDepth(TreeNode root) {
        TreeNode curr = root;
        LinkedList<TreeNode> stack = new LinkedList<>();
        int max = 0;
        TreeNode pop = null;
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                stack.push(curr);
                curr = curr.left;
                if (max < stack.size()) {
                    max = stack.size();
                }
            } else {
                TreeNode peek = stack.peek();
                if ( peek.right == null || peek.right == pop ) {
                    pop = stack.pop();
                }else {
                    curr = peek.right;
                }
            }
        }
        return max;
    }

    //使用層序遍歷求樹的最大深度
    public int sequenceMaxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        int depth = 0;
        while ( !queue.isEmpty()) {
            int size = queue.size();
            for (int j = 0; j < size; j++) {
                TreeNode tp = queue.poll();
                if (tp.left != null) {
                    queue.offer(tp.left);
                }
                if (tp.right != null) {
                    queue.offer(tp.right);
                }
                //System.out.print(tp.val + " ");
            }
            //System.out.println();
            depth++;
        }
        return depth;
    }

    //使用遞歸求樹的最小深度
    public int minDepth(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int l = minDepth(node.left);
        int r = minDepth(node.right);
        if (l == 0) {
            return r + 1;
        }
        if (r == 0) {
            return l + 1;
        }

        return Math.min(l,r) + 1;

    }

    //使用層序遍歷求得樹的最小深度
    public int sequenceMinDepth(TreeNode root) {
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        while (!queue.isEmpty()) {
            depth++;
            int size = queue.size();
            for (int i = 0; i < size ; i++) {
                TreeNode poll = queue.poll();
                if (poll.right == null && poll.left == null) {
                    return depth;
                }
                if (poll.left != null) {
                    queue.offer(poll.left);
                }
                if (poll.right != null) {
                    queue.offer(poll.right);
                }
            }
        }
        return depth;
    }

    //翻轉(zhuǎn)二叉樹
    public void rollbackRecursion(TreeNode node) {
        if (node == null) {
            return;
        }
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;

        rollbackRecursion(node.left);
        rollbackRecursion(node.right);
    }


}

Java LeetCode篇-深入了解二叉樹經(jīng)典解法（三種方式實(shí)現(xiàn)：獲取二叉樹的最大深度）,Java LeetCode篇,leetcode,算法,職場(chǎng)和發(fā)展,java,鏈表文章來源地址http://www.zghlxwxcb.cn/news/detail-753565.html

到了這里，關(guān)于Java LeetCode篇-深入了解二叉樹經(jīng)典解法（三種方式實(shí)現(xiàn)：獲取二叉樹的最大深度）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！