当前位置：首页 > news >正文

力扣104. 二叉树的最大深度（java，DFS，BFS解法）

news 来源：原创 2024/5/20 15:08:41

Problem: 104. 二叉树的最大深度

文章目录

思路和解法
复杂度
Code

思路和解法

DFS

递归处理，退出条件为节点为空，归的过程每次取出当前节点左右子树的最大深度加一

BFS

经典的借助一个队列实现的BFS，用一个变量记录当前的最大层数，在循环实现出队当前节点和添加当前层节点的下一层后将最大层数加一

复杂度

DFS

时间复杂度:

$O (n)$

空间复杂度:

$O (n)$

BFS

时间复杂度:

$O (n)$

空间复杂度:

$O (n)$

Code

DFS


/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {//DFS//Time Complexity: O(n)//Space Complexity: O(n) public int maxDepth(TreeNode root) {//退出条件if (root == null) return 0;return Math.max(maxDepth(root.left),maxDepth(root.right)) + 1;}
}

BFS


/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {//BFS//Time Complexity: O(n)//Space Complexity: O(n)public int maxDepth(TreeNode root) {if (root == null) return 0;Queue<TreeNode> queue = new LinkedList<>();List<Integer> res = new ArrayList<>();queue.add(root);//记录层数int level = 0;while (!queue.isEmpty()) {int curLevelSize = queue.size();for (int i = 0;i < curLevelSize; ++i) {TreeNode curLevelNode = queue.poll();if (curLevelNode.left != null) {queue.add(curLevelNode.left);}if (curLevelNode.right != null) {queue.add(curLevelNode.right);}}//层数加一level++;}return level;}
}