104. 二叉树的最大深度简单给定一个二叉树root返回其最大深度。二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。示例 1输入root [3,9,20,null,null,15,7] 输出3示例 2输入root [1,null,2] 输出2提示树中节点的数量在[0, 104]区间内。-100 Node.val 100 核心笔记二叉树的最大深度 (Maximum Depth of Binary Tree)1. 核心思想 (一句话总结)“向左右下属汇报工作我的高度 max(左下属高度, 右下属高度) 1 (我这一层)。”这是一个典型的后序遍历 (Post-order Traversal)模型先求左子树的深度。再求右子树的深度。最后结合两者算出自己的深度。2. 算法流程 (递归三步曲)终止条件 (Base Case)如果root null说明到了空节点叶子节点的下一层深度为0。递推 (Recurse)int l maxDepth(root.left)int r maxDepth(root.right)回归 (Return)返回Math.max(l, r) 1。这个1代表当前节点本身贡献的一层高度。 代码回忆清单// 题目LC 104. Maximum Depth of Binary Tree class Solution { public int maxDepth(TreeNode root) { // 1. 递归终止条件越过叶子节点高度归零 if (root null) { return 0; } // 2. 问左孩子有多高 int lDepth maxDepth(root.left); // 3. 问右孩子有多高 int rDepth maxDepth(root.right); // 4. 选高的那个加上自己这一层汇报给上级 return Math.max(lDepth, rDepth) 1; } }⚡ 快速复习 CheckList (易错点 扩展)[ ]DFS vs BFSDFS (本解法)代码短$O(H)$ 空间栈深度。BFS (层序遍历)使用Queue。每遍历完一层depth。虽然代码长一点但思路也很直观。如果面试官问“不用递归怎么做”就写 BFS。[ ]时间复杂度因为每个节点都必须被访问一次才能确定最大深度。[ ]空间复杂度。平均情况 $O(\log N)$最坏情况退化成链表 $O(N)$。️ 数字演练树结构3 / \ 9 20 / \ 15 7maxDepth(9): 左null(0), 右null(0) -max(0,0)11。maxDepth(15):max(0,0)11。maxDepth(7):max(0,0)11。maxDepth(20): 左(15返回1), 右(7返回1) -max(1,1)12。maxDepth(3): 左(9返回1), 右(20返回2) -max(1,2)13。结果3。