力扣|力扣 - 剑指 Offer 55 - I. 二叉树的深度力扣-剑指Offer55-I.二叉树的深度

题目 【力扣|力扣 - 剑指 Offer 55 - I. 二叉树的深度】剑指 Offer 55 - I. 二叉树的深度
思路1（DFS）

后续遍历吧，先遍历到最深（递归到末尾返回0），然后从后面一步一步比较取大的值返回，每次返回层数都加1，
执行流程是怎样的：比如其中一个节点左子树为空，右子树有一个叶子节点，那么 0 > 1 ，肯定选 1 ，再加上当前一层 1 ，返回 2 给父节点；然后到了父节点对两个子节点的比较，其中一个节点就是刚才的 2 ，如果另一个返回的深度为4，那么就取 4 ，再加上当前的 1 返回 5 给它的父节点……直到返回到根节点，此时就得到了二叉树的最大深度

代码

class Solution { public int maxDepth(TreeNode root) { return dfs(root); }public int dfs(TreeNode root) { if (root == null) { return 0; }// 获取左子树和右子树的深度 int l = dfs(root.left); int r = dfs(root.right); // 取其中较大的一个深度，并且加上当前一层 1 传递给父节点 return Math.max(l, r) + 1; } }

复杂度分析

时间复杂度：\(O(N)\)
空间复杂度：\(O(N)\)

思路2（BFS）

BFS/广度优先遍历，即层序遍历，这种可能会更好理解一点，这种解法思路就是每次遍历一层，层数res就加 1，直到遍历到最后一层，此时res就是二叉树的最大深度了
使用队列存储节点，每次循环先计算队列中有几个节点（就是每层的节点个数），然后将这些节点一次性出队，同时还要判断出队的节点是否有子节点，如果有就入队，这就算完成了一层的遍历……直到遍历到最后一层

代码

class Solution { public int maxDepth(TreeNode root) { if (root == null) { return 0; }int res = 0; Queue queue = new LinkedList<>(); queue.offer(root); // 层序遍历/广度优先遍历/BFS 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++; }return res; } }

复杂度分析