# 0104. 二叉樹的最大深度 ## 題目地址（104. 二叉樹的最大深度） <https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/description/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個二叉樹，找出其最大深度。 二叉樹的深度為根節點到最遠葉子節點的最長路徑上的節點數。 說明: 葉子節點是指沒有子節點的節點。 示例： 給定二叉樹 [3,9,20,null,null,15,7]， 3 / \ 9 20 / \ 15 7 返回它的最大深度 3 。 ``` ``` ## 前置知識 - [遞歸](https://github.com/azl397985856/leetcode/blob/master/thinkings/dynamic-programming.md) ## 公司 - 阿里 - 騰訊 - 百度 - 字節 - apple - linkedin - uber - yahoo ## 思路 由于樹是一種遞歸的數據結構，因此用遞歸去解決的時候往往非常容易，這道題恰巧也是如此， 用遞歸實現的代碼如下： ``` <pre class="calibre18">``` <span class="hljs-keyword">var</span> maxDepth = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">root</span>) </span>{ <span class="hljs-keyword">if</span> (!root) <span class="hljs-keyword">return</span> <span class="hljs-params">0</span>; <span class="hljs-keyword">if</span> (!root.left && !root.right) <span class="hljs-keyword">return</span> <span class="hljs-params">1</span>; <span class="hljs-keyword">return</span> <span class="hljs-params">1</span> + <span class="hljs-params">Math</span>.max(maxDepth(root.left), maxDepth(root.right)); }; ``` ``` 如果使用迭代呢？ 我們首先應該想到的是樹的各種遍歷，由于我們求的是深度，因此 使用層次遍歷（BFS）是非常合適的。 我們只需要記錄有多少層即可。相關思路請查看[binary-tree-traversal](binary-tree-traversal.html) ## 關鍵點解析 - 隊列 - 隊列中用 Null(一個特殊元素)來劃分每層，或者在對每層進行迭代之前保存當前隊列元素的個數（即當前層所含元素個數） - 樹的基本操作- 遍歷 - 層次遍歷（BFS） ## 代碼 - 語言支持：JS，C++，Python JavaScript Code: ``` <pre class="calibre18">``` <span class="hljs-title">/* * @lc app=leetcode id=104 lang=javascript * * [104] Maximum Depth of Binary Tree */</span> <span class="hljs-title">/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */</span> <span class="hljs-title">/** * @param {TreeNode} root * @return {number} */</span> <span class="hljs-keyword">var</span> maxDepth = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">root</span>) </span>{ <span class="hljs-keyword">if</span> (!root) <span class="hljs-keyword">return</span> <span class="hljs-params">0</span>; <span class="hljs-keyword">if</span> (!root.left && !root.right) <span class="hljs-keyword">return</span> <span class="hljs-params">1</span>; <span class="hljs-title">// 層次遍歷 BFS</span> <span class="hljs-keyword">let</span> cur = root; <span class="hljs-keyword">const</span> queue = [root, <span class="hljs-params">null</span>]; <span class="hljs-keyword">let</span> depth = <span class="hljs-params">1</span>; <span class="hljs-keyword">while</span> ((cur = queue.shift()) !== <span class="hljs-params">undefined</span>) { <span class="hljs-keyword">if</span> (cur === <span class="hljs-params">null</span>) { <span class="hljs-title">// 注意??： 不處理會無限循環，進而堆棧溢出</span> <span class="hljs-keyword">if</span> (queue.length === <span class="hljs-params">0</span>) <span class="hljs-keyword">return</span> depth; depth++; queue.push(<span class="hljs-params">null</span>); <span class="hljs-keyword">continue</span>; } <span class="hljs-keyword">const</span> l = cur.left; <span class="hljs-keyword">const</span> r = cur.right; <span class="hljs-keyword">if</span> (l) queue.push(l); <span class="hljs-keyword">if</span> (r) queue.push(r); } <span class="hljs-keyword">return</span> depth; }; ``` ``` C++ Code: ``` <pre class="calibre18">``` <span class="hljs-title">/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */</span> <span class="hljs-keyword">class</span> Solution { <span class="hljs-keyword">public</span>: <span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">maxDepth</span><span class="hljs-params">(TreeNode* root)</span> </span>{ <span class="hljs-keyword">if</span> (root == <span class="hljs-params">nullptr</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">0</span>; <span class="hljs-keyword">auto</span> q = <span class="hljs-params">vector</span><TreeNode*>(); <span class="hljs-keyword">auto</span> d = <span class="hljs-params">0</span>; q.push_back(root); <span class="hljs-keyword">while</span> (!q.empty()) { ++d; <span class="hljs-keyword">auto</span> sz = q.size(); <span class="hljs-keyword">for</span> (<span class="hljs-keyword">auto</span> i = <span class="hljs-params">0</span>; i < sz; ++i) { <span class="hljs-keyword">auto</span> t = q.front(); q.erase(q.begin()); <span class="hljs-keyword">if</span> (t->left != <span class="hljs-params">nullptr</span>) q.push_back(t->left); <span class="hljs-keyword">if</span> (t->right != <span class="hljs-params">nullptr</span>) q.push_back(t->right); } } <span class="hljs-keyword">return</span> d; } }; ``` ``` Python Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxDepth</span><span class="hljs-params">(self, root: TreeNode)</span> -> int:</span> <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> root: <span class="hljs-keyword">return</span> <span class="hljs-params">0</span> q, depth = [root, <span class="hljs-keyword">None</span>], <span class="hljs-params">1</span> <span class="hljs-keyword">while</span> q: node = q.pop(<span class="hljs-params">0</span>) <span class="hljs-keyword">if</span> node: <span class="hljs-keyword">if</span> node.left: q.append(node.left) <span class="hljs-keyword">if</span> node.right: q.append(node.right) <span class="hljs-keyword">elif</span> q: q.append(<span class="hljs-keyword">None</span>) depth += <span class="hljs-params">1</span> <span class="hljs-keyword">return</span> depth ``` ``` **復雜度分析** - 時間復雜度：O(N)O(N)O(N) - 空間復雜度：O(N)O(N)O(N) ## 相關題目 - [102.binary-tree-level-order-traversal](102.binary-tree-level-order-traversal.html) - [103.binary-tree-zigzag-level-order-traversal](103.binary-tree-zigzag-level-order-traversal.html) 大家對此有何看法，歡迎給我留言，我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫：<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。