https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/description/
给定一个二叉树，找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明: 叶子节点是指没有子节点的节点。 示例： 给定二叉树 [3,9,20,null,null,15,7]， 3 / \ 9 20 / \ 15 7 返回它的最大深度 3 。 - 阿里
- 腾讯
- 百度
- 字节
- apple
- uber
- yahoo
由于树是一种递归的数据结构，因此用递归去解决的时候往往非常容易，这道题恰巧也是如此，
- 用递归实现的代码如下：
varmaxDepth=function(root){if(!root)return0;if(!root.left&&!root.right)return1;return1+Math.max(maxDepth(root.left),maxDepth(root.right));};如果使用迭代呢？ 我们首先应该想到的是树的各种遍历，由于我们求的是深度，因此 使用层次遍历（BFS）是非常合适的。 我们只需要记录有多少层即可。相关思路请查看binary-tree-traversal
- 队列
- 队列中用 Null(一个特殊元素)来划分每层，或者在对每层进行迭代之前保存当前队列元素的个数（即当前层所含元素个数）
- 树的基本操作- 遍历 - 层次遍历（BFS）
- 语言支持：JS，C++，Java，Python, Go, PHP
JS Code:
/* * @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} */varmaxDepth=function(root){if(!root)return0;if(!root.left&&!root.right)return1;// 层次遍历 BFSletcur=root;constqueue=[root,null];letdepth=1;while((cur=queue.shift())!==undefined){if(cur===null){// 注意⚠️： 不处理会无限循环，进而堆栈溢出if(queue.length===0)returndepth;depth++;queue.push(null);continue;}constl=cur.left;constr=cur.right;if(l)queue.push(l);if(r)queue.push(r);}returndepth;};C++ Code:
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * };*/classSolution { public:intmaxDepth(TreeNode* root) { if (root == nullptr) return0; 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; } };Java Code:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */classSolution { publicintmaxDepth(TreeNoderoot) { if(root == null) { return0; } // 队列Queue<TreeNode> queue = newLinkedList<TreeNode>(); queue.offer(root); intres = 0; // 按层扩展while(!queue.isEmpty()) { // 拿出该层所有节点，并压入子节点intsize = queue.size(); while(size > 0) { TreeNodenode = queue.poll(); if(node.left != null) { queue.offer(node.left); } if(node.right != null) { queue.offer(node.right); } size-=1; } // 统计层数res +=1; } returnres; } }Python Code:
classSolution: defmaxDepth(self, root: TreeNode) ->int: ifnotroot: return0q, depth= [root, None], 1whileq: node=q.pop(0) ifnode: ifnode.left: q.append(node.left) ifnode.right: q.append(node.right) elifq: q.append(None) depth+=1returndepthGo Code:
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */// BFSfuncmaxDepth(root*TreeNode) int { ifroot==nil { return0 } depth:=1q:= []*TreeNode{root, nil} // queuevarnode*TreeNodeforlen(q) >0 { node, q=q[0], q[1:] // popifnode!=nil { ifnode.Left!=nil { q=append(q, node.Left) } ifnode.Right!=nil { q=append(q, node.Right) } } elseiflen(q) >0 { // 注意要判断队列是否只有一个 nilq=append(q, nil) depth++ } } returndepth }PHP Code:
/** * Definition for a binary tree node. * class TreeNode { * public $val = null; * public $left = null; * public $right = null; * function __construct($value) { $this->val = $value; } * } */class Solution { /** * @param TreeNode $root * @return Integer */functionmaxDepth($root) { if (!$root) return0; $depth = 1; $arr = [$root, null]; while ($arr) { /** @var TreeNode $node */$node = array_shift($arr); if ($node) { if ($node->left) array_push($arr, $node->left); if ($node->right) array_push($arr, $node->right); } elseif ($arr) { $depth++; array_push($arr, null); } } return$depth; } }复杂度分析
- 时间复杂度：$O(N)$
- 空间复杂度：$O(N)$
大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
