夫陶公清風千古，余又何人，敢稱庶幾

---

文章目錄

• • • 題目描述
    • 題解
    • 代碼
    • • 創建一棵二叉樹
      • 深度優先
      • 廣度優先
    • 測試

題目描述

📖

• 給定一個二叉樹，找出其最大深度。

• 二叉樹的深度為根節點到最遠葉子節點的最長路徑上的節點數。

說明: 葉子節點是指沒有子節點的節點。

示例：

🎨給定二叉樹 [3,9,20,null,null,15,7]

題解

💡 當看到這一類題目，首先想到的就是遍歷求解，想到的求解方法主要是深度優先和廣度優先。題目要求求最大深度，我們只需比較左樹和右樹各分支的深度（節點個數），把最大值返回即可，深度優先我們可以直接使用遞歸，一行代碼就可以解決，而使用廣度優先我們需要借助一個棧實現，具體請看下面介紹。

代碼

創建一棵二叉樹

📖

🎨 根據題意，我們傻瓜式地創建一棵節點為：[3,9,20,null,null,15,7]的二叉樹，具體創建方法如下：

首先我們創建5個對象，代表5個節點。TreeNode root = new TreeNode(3)表示創建根節點，值為3，其余的都是子節點。

??

public static TreeNode createBinaryTree() {TreeNode root = new TreeNode(3);TreeNode node1 = new TreeNode(9);TreeNode node2 = new TreeNode(20);TreeNode node3 = new TreeNode(15);TreeNode node4 = new TreeNode(7);root.left = node1;root.right = node2;node2.left = node3;node2.right = node4;return root;}

• 💡root.left = node1：把節點node1的引用(值為9)賦給根節點(值為3)的左孩子,如下圖所示：

• 💡 root.right = node2：把節點node2引用(值為20)賦給根節點(值為3)的右孩子,如下圖所示：

• 💡 node2.left = node3：把節點node3引用(值為15)賦給node2節點(值為20)的左孩子,如下圖所示：

• 💡 node2.right = node4：把節點node4引用(值為7)賦給node2節點(值為20)的右孩子,如下圖所示：

深度優先

??

public static int maxDepthDFS(TreeNode root) {return root == null ? 0 : Math.max(maxDepthDFS(root.left), maxDepthDFS(root.right)) + 1;} }

廣度優先

??

public static int maxDepthBFS(TreeNode root) {if (root == null) {return 0;}int ans = 0;Queue<TreeNode> queue = new LinkedList<TreeNode>();queue.offer(root);while (!queue.isEmpty()) {int size = queue.size();while (size > 0) {TreeNode node = queue.poll();if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}size--;}ans++;}return ans;}

測試

🎨 測試用例：

[3,9,20,null,null,15,7]

??測試代碼：

public static void main(String[] args) {TreeNode root = BinaryTree.createBinaryTree();System.out.println("深度優先 最大深度：" + maxDepthDFS(root));System.out.println("廣度優先 最大深度：" + maxDepthBFS(root)); }

??測試結果：

深度優先 最大深度：3 廣度優先 最大深度：3

---

LeetCode:104. 二叉樹的最大深度

總結

以上是生活随笔為你收集整理的104. 二叉树的最大深度【LeetCode】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。