🔥博客主頁：?【小扳_-CSDN博客】
?感謝大家點贊👍收藏?評論???

文章目錄

? ? ? ? 1.0 對稱二叉樹

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

---

? ? ? ? 1.0 對稱二叉樹

題目：

????????給你一個二叉樹的根節(jié)點?root?， 檢查它是否軸對稱。

示例 1：

輸入：root = [1,2,2,3,4,4,3]
輸出：true

示例 2：

輸入：root = [1,2,2,null,3,null,3]
輸出：false

OJ鏈接：

101.?對稱二叉樹

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

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

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

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

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

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

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

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

    //判斷對稱二叉樹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 二叉樹的最大深度

題目：

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

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

示例 1：

輸入：root = [3,9,20,null,null,15,7]
輸出：3

OJ鏈接：

104.?二叉樹的最大深度

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

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

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

? ? ? ? 2.2 代碼實現(xiàn)：使用遞歸實現(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 使用非遞歸實現(xiàn)獲取二叉樹的最大深度思路

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

? ? ? ? 2.4 代碼實現(xiàn)：使用非遞歸實現(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)然，這個時間復(fù)雜度比使用遞歸實現(xiàn)的要大，效率不如使用遞歸的實現(xiàn)二叉樹最大深度。

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

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

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

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

? ? ? ? 2.6 代碼實現(xiàn)：使用層序遍歷實現(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 二叉樹的最小深度

題目：

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

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

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

示例 1：

輸入：root = [3,9,20,null,null,15,7]
輸出：2

OJ鏈接：

111.?二叉樹的最小深度

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

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

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

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

? ? ? ? 3.2?代碼實現(xiàn)：使用遞歸實現(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?使用層序遍歷實現(xiàn)獲取二叉樹的最小深度思路

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

? ? ? ? 3.4?代碼實現(xiàn)：使用層序遍歷實現(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é)點?root，請左右翻轉(zhuǎn)這棵二叉樹，并返回其根節(jié)點。

示例 1：

輸入：root = [5,7,9,8,3,2,4]
輸出：[5,9,7,4,2,3,8]

OJ鏈接：

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

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

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

? ? ? ? 4.2 代碼實現(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)典解法的完整代碼

回顧本章代碼，進一步鞏固：

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;}//遞歸實現(xiàn)前序遍歷public void prevRecursion(TreeNode node) {if (node == null) {return;}System.out.print(node.val + " ");prevRecursion(node.left);prevRecursion(node.right);}//遞歸實現(xiàn)中序遍歷public void midRecursion(TreeNode node) {if (node == null) {return;}midRecursion(node.left);System.out.print(node.val + " ");midRecursion(node.right);}//遞歸實現(xiàn)后序遍歷public void postRecursion(TreeNode node) {if (node == null) {return;}postRecursion(node.left);postRecursion(node.right);System.out.print(node.val + " ");}//非遞歸實現(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;}//非遞歸實現(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();}//非遞歸實現(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;}//判斷對稱二叉樹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);}}