0104. 二叉树的最大深度 · ttttt

# 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">``` var maxDepth = function (root) { if (!root) return 0; if (!root.left && !root.right) return 1; return 1 + Math.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">``` /* * @lc app=leetcode id=104 lang=javascript * * [104] Maximum Depth of Binary Tree */ /** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * @param {TreeNode} root * @return {number} */ var maxDepth = function (root) { if (!root) return 0; if (!root.left && !root.right) return 1; // 层次遍历 BFS let cur = root; const queue = [root, null]; let depth = 1; while ((cur = queue.shift()) !== undefined) { if (cur === null) { // 注意⚠️：不处理会无限循环，进而堆栈溢出 if (queue.length === 0) return depth; depth++; queue.push(null); continue; } const l = cur.left; const r = cur.right; if (l) queue.push(l); if (r) queue.push(r); } return depth; }; ``` ``` C++ Code: ``` <pre class="calibre18">``` /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: int maxDepth(TreeNode* root) { if (root == nullptr) return 0; auto q = vector<TreeNode*>(); auto d = 0; q.push_back(root); while (!q.empty()) { ++d; auto sz = q.size(); for (auto i = 0; i < sz; ++i) { auto t = q.front(); q.erase(q.begin()); if (t->left != nullptr) q.push_back(t->left); if (t->right != nullptr) q.push_back(t->right); } } return d; } }; ``` ``` Python Code: ``` <pre class="calibre18">``` class Solution: def maxDepth(self, root: TreeNode) -> int: if not root: return 0 q, depth = [root, None], 1 while q: node = q.pop(0) if node: if node.left: q.append(node.left) if node.right: q.append(node.right) elif q: q.append(None) depth += 1 return 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 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)