leetcode104：二叉树的最大深度 #42
Comments
解答：递归const maxDepth = function(root) {
if(!root) return 0
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right))
};复杂度分析： 时间复杂度：O(n) 空间复杂度： O(logn) |
二叉树的最大深度主要考察的是深度优先遍历 function TreeDepth(node) {
// 最大深度等于左子树或者右子树的最大值加1
return !node ? 0 : Math.max(TreeDepth(node.left), TreeDepth(node.right)) + 1
} |
|
题干好像有问题，与这篇文章中定义的节点深度有点出入：https://mp.weixin.qq.com/s/-PlTxNeMpGop2I9mwVaJhw，节点的深度 ：从根节点到该节点所经历的边的个数 |
|
@XuShunyi 你说的没错，节点的深度是这么定义的，但是题干问的是树的最大深度，就是指根节点到最远叶子节点的边的数量，也就是最远的子节点的深度。最远的子节点的深度=树的最大深度 |
|
@luweiCN ,你看下例子里的那棵树，根节点3到叶子节点7的边的数量不是2吗，题中说是3，按你说的好像也不对 |
|
@XuShunyi 是的哦，是有点问题，我找到了另一种定义。
|
分析
var maxDepth = function (root) {
if (root == null) return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}; |
|
递归,记录最大长度 function maxTreeCount(root){
if(!root) return 0
let max = 1
TreeCount(root, 1)
function TreeCount(node, num){
max= Math.max(max, num++)
if(node.left)TreeCount(node.left, num)
if(node.right)TreeCount(node.right, num)
}
return max
}迭代实现 function maxTreeCount(root){
if(!root) return 0
let max = 1
const stack = [];
root.index = 1
stack.push(root)
while(stack.length>0){
const curNode = stack.pop()
max = Math.max(max, curNode.index)
if(curNode.left){
curNode.left.index = curNode.index+1
stack.push(curNode.left)
}
if(curNode.right){
curNode.right.index = curNode.index+1
stack.push(curNode.right)
}
}
return max
} |
二叉树的最大深度指的是包括根节点的呀。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。 |
BFSvar maxDepth = function(root) {
if(!root) return 0;
let max = 0;
let queue = [root];
while(queue.length) {
max+=1;
let len = queue.length;
for(let i = 0;i<len; i++) {
let node = queue.shift();
if(node.left) queue.push(node.left);
if(node.right) queue.push(node.right);
}
}
return max;
}; |
题目地址（104. 二叉树的最大深度）https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/description/ 题目描述前置知识公司
思路由于树是一种递归的数据结构，因此用递归去解决的时候往往非常容易，这道题恰巧也是如此，
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));
};如果使用迭代呢？ 我们首先应该想到的是树的各种遍历，由于我们求的是深度，因此 关键点解析
代码
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}
*/
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: /**
* 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;
}
};Java Code: /**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
if(root == null)
{
return 0;
}
// 队列
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
int res = 0;
// 按层扩展
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-=1;
}
// 统计层数
res +=1;
}
return res;
}
}Python Code: 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 depthGo Code: /**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
// BFS
func maxDepth(root *TreeNode) int {
if root == nil {
return 0
}
depth := 1
q := []*TreeNode{root, nil} // queue
var node *TreeNode
for len(q) > 0 {
node, q = q[0], q[1:] // pop
if node != nil {
if node.Left != nil {
q = append(q, node.Left)
}
if node.Right != nil {
q = append(q, node.Right)
}
} else if len(q) > 0 { // 注意要判断队列是否只有一个 nil
q = append(q, nil)
depth++
}
}
return depth
}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
*/
function maxDepth($root)
{
if (!$root) return 0;
$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;
}
}复杂度分析
相关题目大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。 |
|
数的深度是这样求 const maxDepth = (root) => {
if(!root) return 0
let max = 0
for(const p of root.children) {
const depth = maxDepth(p) + 1
if(depth > max) {
max = depth
}
}
return max
}二叉树的深度变换下 const maxDepth = (root) => {
if(!root) return 0
if (!root.left && !root.right) return 1;
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树
[3,9,20,null,null,15,7]，返回它的最大深度 3
附赠leetcode地址：leetcode
The text was updated successfully, but these errors were encountered: