1.深度與高度
- 二叉樹節點的深度：指從根節點到該節點的最長簡單路徑邊的條數或者節點數（取決于深度從0開始還是從1開始）
- 二叉樹節點的高度：指從該節點到葉子節點的最長簡單路徑邊的條數后者節點數（取決于高度從0開始還是從1開始）
根節點的高度就是二叉樹的最大深度！！！
2.二叉樹的最大深度
上面已經介紹了深度，所以我們這邊求解最大深度只需要計算左右子樹之中最大的深度+1,，
我們首先使用遞回求解，根據上面思路很容易寫出代碼：
class solution { public int maxDepth(TreeNode root) { if (root == null) { return 0; } int leftDepth = maxDepth(root.left); int rightDepth = maxDepth(root.right); return Math.max(leftDepth, rightDepth) + 1; } }
除了遞回，我們還可以使用層序遍歷進行求解，我們一層一層的遍歷，直到遍歷到最后一層，即可求出最大深度，
我們只需要在層序遍歷代碼里面加個變數計數即可，代碼如下：
class solution { public int maxDepth(TreeNode root) { if(root == null) { return 0; } Deque<TreeNode> deque = new LinkedList<>(); deque.offer(root); int depth = 0; while (!deque.isEmpty()) { int size = deque.size(); depth++; for (int i = 0; i < size; i++) { TreeNode node = deque.poll(); if (node.left != null) { deque.offer(node.left); } if (node.right != null) { deque.offer(node.right); } } } return depth; } }
3.二叉樹的最小深度
剛剛做完最大深度，感覺最小深度也是一樣，只需要將遞回里面最大換成最小即可，
這就大錯特錯了，第一次我也犯了這個錯，說到底就是最小深度是從根節點到最近葉子節點的最短路徑上的節點數量，只有到了葉子節點才可以！！！所以這里我們多了幾種情況進行判斷，
如果左子樹為空，右子樹不為空，說明最小深度是 1 + 右子樹的深度，反之，右子樹為空，左子樹不為空，最小深度是 1 + 左子樹的深度， 最后如果左右子樹都不為空，回傳左右子樹深度最小值 + 1 ，
根據思路我們可以得到以下代碼：
class Solution { public int minDepth(TreeNode root) { if (root == null) { return 0; } int leftDepth = minDepth(root.left); int rightDepth = minDepth(root.right); if (root.left == null) { return rightDepth + 1; } if (root.right == null) { return leftDepth + 1; } // 左右結點都不為null return Math.min(leftDepth, rightDepth) + 1; } }
同樣我們也可以使用層次遍歷求解，但是和上面不同，既然求最小，那么只要訪問到了葉子節點就回傳，就已經到了最小深度處，所以有如下代碼：
class Solution { public int minDepth(TreeNode root) { if (root == null) { return 0; } Deque<TreeNode> deque = new LinkedList<>(); deque.offer(root); int depth = 0; while (!deque.isEmpty()) { int size = deque.size(); depth++; for (int i = 0; i < size; i++) { TreeNode poll = deque.poll(); if (poll.left == null && poll.right == null) { // 是葉子結點，直接回傳depth，因為從上往下遍歷，所以該值就是最小值 return depth; } if (poll.left != null) { deque.offer(poll.left); } if (poll.right != null) { deque.offer(poll.right); } } } return depth; } }
通過這兩題又了解了二叉樹，以后遇到類似的題目都不怕了！！！
不了解層序遍歷的可以看我之前的博客 Here
4.LeetCode鏈接
最大深度：https://leetcode.cn/problems/maximum-depth-of-binary-tree/
最小深度：https://leetcode.cn/problems/minimum-depth-of-binary-tree/
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/540286.html
標籤：其他
上一篇：Tarjan演算法求割點