---

前言

---

提示：我的整個生命，只是一場為了提升社會地位的低俗斗爭。--埃萊娜·費蘭特《失蹤的孩子》

這一關(guān)我們看一些比較特別的題目，關(guān)于二叉樹的深度和高度問題。這些對遞歸的考察更高些，要注意了。

給你一個二叉樹：

我們看下力扣的相關(guān)題目，這些是關(guān)于深度和高度的問題。

推薦題目????：

104. 二叉樹的最大深度 - 力扣（LeetCode）

110. 平衡二叉樹 - 力扣（LeetCode）

111. 二叉樹的最小深度 - 力扣（LeetCode）

1. 最大深度問題

參考題目介紹：104. 二叉樹的最大深度 - 力扣（LeetCode）


首先最大深度：根節(jié)點到最遠葉子節(jié)點的最長路徑上的節(jié)點數(shù)。說明葉子節(jié)點是沒有子節(jié)點的。

我們看看下面這些。（上圖的最大深度為3）

對于node(3)，最大深度自然是左右子節(jié)點+1，左右子節(jié)點有可能為空，只要有一個，樹的最大高度就是1 + 1 = 2。然后再增加幾個節(jié)點：

很顯然相對于node(20)，最大的深度自然是左右子節(jié)點+1，左右子節(jié)點有可能為空，只要右一個，樹的最大高度就是1 + 1 = 2，用代碼表示就是：

int depth = 1 + math(leftDepth,rightDepth);

對于3，則是左右子樹深度最大的那個再加1，具體誰的更大，則不必管旭，所以對于node(3)的邏輯判斷就是：

int leftDepth =  getDepth(root.left); //左
int rightDepth =  getDepth(root.right); // 右
int depth = 1 + math(leftDept,rightDept); // 中

那么什么時候結(jié)束呢？這里仍然是root == null 返回0就行了，至于入?yún)?#xff0c;自然是要處理的子樹的根節(jié)點root，而返回值則是當(dāng)前root所在子樹的最大高度，所以合在一起就是：

	/*** 通過遞歸計算二叉樹的深度** @param root* @return*/public static int maxDepth_1(TreeNode root) {if(root == null) {return 0;}int leftDepth = maxDepth_1(root.left);int rightDepth = maxDepth_1(root.right);return Math.max(leftDepth, rightDepth) + 1;}

上面代碼先拿到左右子樹的結(jié)果，再計算Math.max(left,right) + 1，本質(zhì)上和后序遍歷一樣，一次者可以看做事后序遍歷的擴展問題。

我們繼續(xù)看這個題目，如果我們確定樹最大有幾層是不是也確定了最大深度呢？當(dāng)然，另一個思路不就來了，我們直接套用層序遍歷的代碼：

具體細節(jié)注意一下：我們這里獲取層數(shù)，每獲取一層，就加一。

    /*** 通過層次遍歷來求最大深度** @param root* @return*/public static int maxDepth_2(TreeNode root) {// 校驗參數(shù)if (root == null){return 0;}// 創(chuàng)建空間int res = 0;Queue<TreeNode> queue = new LinkedList<TreeNode>();// 根節(jié)點入隊，不斷的遍歷根節(jié)點queue.offer(root);while(!queue.isEmpty()){// 獲取到每層多少個int size = queue.size();//	size == 0 說明這一層遍歷完了while(size > 0){// 遍歷TreeNode node = queue.poll();if (node.left != null){queue.offer(node.left);}if (node.right != null){queue.offer(node.right);}size--;}res++;}return res;}

2. 判斷平衡樹

參考題目介紹：110. 平衡二叉樹 - 力扣（LeetCode）

補充一個知識點：高度和深度怎么區(qū)分?

• 二叉樹節(jié)點的深度：從根節(jié)點到該節(jié)點的最長簡單路徑邊的條數(shù)。
• 二叉樹節(jié)點的高度：從該節(jié)點到葉子節(jié)點的最長簡單路徑邊的條數(shù)。

關(guān)于根節(jié)點的深度是1還是0的問題，不同的地方標準不一樣，力扣的題目中都是以根節(jié)點的深度為1，其他的我們先不管。

我們接著看一下這個問題：

很顯然只要有兩次的時候一定是平衡的，因為對于node(3)，左右孩子如果只有一個，呢么高度差就是1；如果左右孩子都沒有或者都有，則高度差為0。但是如果再加一層呢？

看下圖：

對于node(3)，需要同時知道自己左右子樹的最大高度差是否< 2.

• 當(dāng)節(jié)點root左/右子樹的高度差 < 2，則返回節(jié)點root的左右子樹中最大高度+1（max（left,right) + 1);參考上面的深度和高度對比圖思考下，這里為什么取最大高度？
• 當(dāng)節(jié)點root左/右子樹的高度差 >= 2；則返回-1，代表此樹已經(jīng)不是平衡樹了。

也是就是說：

int left = recur(root.left);
int right = recur(root.right);
return Math.abs(left - right) < 2 ? Math.max(left,right) + 1:-1; 

我們此時已經(jīng)寫出了核心代碼，假設(shè)子樹已經(jīng)不平衡了，我們就不需要再遞歸下去而是直接返回就行了。例如這個樹中的節(jié)點20：

綜合考慮幾種情況，我們看下完整的代碼：

	/*** 方法1 自下而上** @param root* @return*/public static boolean isBalanced_1(TreeNode root) {return recur(root) == -1;}public static int recur(TreeNode root) {if (root == null){return 0;}int left = recur(root.left);if (left == -1){return -1;}int right = recur(root.right);if (right == -1){return -1;}return Math.abs(left - right) < 2 ? Math.max(left,right) + 1: -1;}

---

/*** 2.自上而下** @param root* @return*/public static boolean isBalanced_2(TreeNode root) {if (root == null){return true;}return Math.abs(depth(root.left) - depth(root.right)) <= 1 && isBalanced_2(root.left) && isBalanced_2(root.right);}public static int depth(TreeNode root){if (root == null){return 0;}return Math.max(depth(root.left),depth(root.right)) + 1;}

3. 最小深度

參考題目介紹：111. 二叉樹的最小深度 - 力扣（LeetCode）

既然有最大深度，可能會有最小深度？這不他就來了，怎么找出最小深度呢？

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

看下下面這個特殊例子： 答案是 2 【說明】：葉子節(jié)點是指沒有子節(jié)點的節(jié)點。

前面兩道題涉及到最大深度，這里講max改成min是不是就可以解決了呢？ 不行，你注意看上圖：

這里的關(guān)鍵問題是題目中說的：最小深度是從根節(jié)點到最近葉子節(jié)點的最短路徑上的節(jié)點數(shù)量，也就是說最小深度的一層必須要有葉子節(jié)點，不能直接使用。

這里的核心問題仍然是終止條件分析：

• 如果左子樹為空，右子樹不為空，說明最小深度是1 + 右子樹的深度。
• 反之，右子樹為空，左子樹不為空，最小深度1 + 左子樹的深度。

最后如果左右子樹都不空，返回左右子樹深度最小值+1。

我們看下代碼展示😎：

	/*** 通過遞歸計算二叉樹的最小** @param root* @return*/public static int minDepth_1(TreeNode root) {if (root == null){return 0;}// 根if (root.left == null && root.right == null){return 1;}// 左int min_depth = Integer.MAX_VALUE;if (root.left != null){min_depth = Math.min(minDepth_1(root.left),min_depth);}// 右if (root.right != null){min_depth = Math.min(minDepth_1(root.right),min_depth);}return min_depth + 1;}

除了遞歸方式，我們也可以采用層次遍歷，只要再遍歷時，第一次遇到葉子節(jié)點就直接返回，其所在的層次就行，我們可以簡單改下層序遍歷的方法：

	/*** 通過層次遍歷來求最大深度** @return*/public static int minDepth_2(TreeNode root) {// 參數(shù)檢驗if (root == null){return 0;}// 創(chuàng)建空間int minDepth = 0;Queue<TreeNode> queue = new LinkedList<>();// 根節(jié)點入隊，不斷循環(huán)遍歷queue.offer(root);while(!queue.isEmpty()){// 獲取隊列的長隊  這個長度說明這一層有多少個節(jié)點int size = queue.size();minDepth++;for(int i = 0; i < size; i++){TreeNode node = queue.poll();if (node.left == null && node.right == null){return minDepth;}if (node.left != null){queue.offer(node.left);}if (node.right != null){queue.offer(node.right);}}}return 0;}

4. N叉樹的最大深度

參考題目介紹：559. N 叉樹的最大深度 - 力扣（LeetCode）

這道題不同的地方是將二叉樹換成了N叉樹，N叉樹的節(jié)點較多，我們使用List存儲，遍歷時采用for即可，我們先看看力扣的N叉樹的定義：

class Node {public int val;public List<Node> children;public Node() {}public Node(int _val) {val = _val;}public Node(int _val, List<Node> _children) {val = _val;children = _children;}
};

這個題的實現(xiàn)和上個題的最大區(qū)別就是在處理子樹的問題上面加了個處理List的for循環(huán)

代碼也很簡單🤔：

	/*** 遞歸求N叉樹的深度* @param root* @return*/public static int maxDepth_N(NTreeNode root) {if (root == null){return 0;}else if (root.children.isEmpty()){return 1;}else{// 處理子樹問題List<Integer> heights = new ArrayList<>();for(NTreeNode item : root.children){heights.add(maxDepth_N(item));}return Collections.max(heights) + 1;}}

當(dāng)然了，本地還可以使用層序遍歷，這個作為拓展感興趣的話可以試試。

---

總結(jié)

提示：二叉樹的深度和高度；N叉樹的深度問題；平衡樹的判斷問題