LeetCode------Maximum Depth of Binary Tree
程序员文章站
2024-02-12 22:42:16
...
求二叉树的最大深度问题用到深度优先搜索DFS,递归的完美应用,跟求二叉树的最小深度问题原理相同。
递归解法
// Maximum Depth of Binary Tree
// 时间复杂度O(n),空间复杂度O(logn)
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}
非递归解法
使用层序遍历二叉树,然后计数总层数,即为二叉树的最大深度。
public class Solution {
public int maxDepth(TreeNode root) {
if (root == null) return 0;
int res = 0;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
++res;
int n = q.size();
for (int i = 0; i < n; ++i) {
TreeNode t = q.poll();
if (t.left != null) q.offer(t.left);
if (t.right != null) q.offer(t.right);
}
}
return res;
}
}
上一篇: 数据库监听
推荐阅读
-
LeetCode------Maximum Depth of Binary Tree
-
Leetcode 104: Maximum Depth of Binary Tree
-
leetcode Maximum Width of Binary Tree
-
LeetCode-297.Serialize and Deserialize Binary Tree(二叉树的序列化和反序列化)
-
【LeetCode】104. Maximum Depth of Binary Tree 二叉树的深度 DFS BFS 递归方式 迭代方式 JAVA
-
LC 297 Serialize and Deserialize Binary Tree
-
leetcode笔记:Invert Binary Tree
-
Convert Sorted Array to Binary Search Tree
-
minimum-depth-of-binary-tree
-
cf438E. The Child and Binary Tree(生成函数 多项式开根 多项式求逆)