Maximum Depth of Binary Tree(二叉树最大深度)
2024-10-07 07:34:08
来源:https://leetcode.com/problems/maximum-depth-of-binary-tree
Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
1. 深度遍历,递归
Java
/**
* 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;
}
int leftDepth = maxDepth(root.left) + 1;
int rightDepth = maxDepth(root.right) + 1;
return leftDepth > rightDepth ? leftDepth : rightDepth;
}
}
Python
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None class Solution(object):
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
left_depth = self.maxDepth(root.left) + 1
right_depth = self.maxDepth(root.right) + 1
return left_depth if left_depth>right_depth else right_depth
2. 广度遍历(逐层遍历),使用队列
Java
/**
* 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) {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
int depth = -1;
queue.offer(root);
TreeNode node = null;
int queueSize = 0;
while(!queue.isEmpty()) {
queueSize = queue.size();
while(queueSize-- > 0) {
node = queue.poll();
if(node == null) {
continue;
}
queue.offer(node.left);
queue.offer(node.right);
}
depth += 1;
}
return depth;
}
}
Python
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None class Solution(object):
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
queue = [root]
depth = -1
while queue:
depth += 1
queue = [kid for node in queue if node for kid in (node.left, node.right)]
return depth
最新文章
- JAVA构造时成员初始化的陷阱
- 图片轮播器bcastr4.swf“&;”符号的问题
- Web调用FastReport的配置问题
- nginx 的动静分离配置(tomcat)
- 用一段JS代码来比较各浏览器的极限内存与运算速度
- 【SMS】移动短信网关返回信息状态代码说明【China Mobile】
- 如何写出优秀的研究论文 Chapter 1. How to Write an A+ Research Paper
- 我忽略了的DOCTYPE!
- (转载)完美解决PHP中文乱码问题
- 【剑指offer】替换字符串中的空格
- Error configuring application listener of class 报错 解决
- Nginx-动态路由升级版
- jmeter监控服务资源
- 【转】CentOS 6.3(x86_32)下安装Oracle 10g R2
- Python:zip 函数的用法
- python一个简单的打包例子
- 软件包管理之rpm与yum
- 使用Java+Kotlin双语言的LeetCode刷题之路(三)
- P3924 康娜的线段树(期望)
- [转]C#使用 Salt + Hash 来为密码加密