CS-Notes 剑指 Offer 55.1 详解：二叉树深度的递归与分层遍历两种解法

CS-Notes 剑指 Offer 55.1 详解二叉树深度的递归与分层遍历两种解法【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes本篇基于 CS-Notes 中剑指 Offer 题解的《55.1 二叉树的深度》一文展开先给出树深度的精确定义与图解示例然后完整继承仓库中的递归解法并逐步剖析其正确性、复杂度与边界情况再补充基于队列分层遍历的迭代解法最后串联仓库中依赖高度自底向上计算思想的 55.2 平衡二叉树问题帮助读者掌握二叉树深度/高度这一高频考点的完整解法体系。一、题目定义什么是一棵树的深度原始题解对题目给出的标准定义是从根结点到叶结点依次经过的结点含根、叶结点形成树的一条路径最长路径的长度为树的深度。也就是说深度不是层数的模糊概念而是结点数一条路径上从根到叶依次经过的结点个数。仓库配图给出了一个典型示例这棵树的最长路径为 1 → 2 → 4或 1 → 2 → 5经过 3 个结点因此深度为 3由该定义可以直接推出两条边界约定这也是写递归代码时最容易被判题系统卡住的细节空树root null的深度为 0。题解代码中root null ? 0 : ...正是这一约定只有根结点的树深度为 1即单个结点的路径长度为 1。二、递归解法仓库原始解法notes/55.1 二叉树的深度.md 给出的解法是标准的后序递归自底向上一行三元表达式即完成public int TreeDepth(TreeNode root) { return root null ? 0 : 1 Math.max(TreeDepth(root.left), TreeDepth(root.right)); }其中TreeNode是剑指 Offer 系列题目的标准结点结构可从仓库各题解的用法中看出均只使用了val、left、right三个成员public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val x; } }逐步拆解把三元表达式展开成显式写法逻辑更清晰public int TreeDepth(TreeNode root) { if (root null) { return 0; // 空树深度为 0 } int leftDepth TreeDepth(root.left); // 左子树的深度 int rightDepth TreeDepth(root.right); // 右子树的深度 return 1 Math.max(leftDepth, rightDepth); // 当前树深度 较深子树的深度 1 }正确性可以这样理解对于任意结点以它为根的子树的深度必然等于它左右两棵子树深度中的较大值加 1加 1 是因为当前结点本身计入路径。而叶结点没有子树这一情形恰好被空子树深度为 0的约定覆盖了对叶结点而言max(0, 0) 1 1与其定义一致。因此整个递归无需为叶结点写单独分支。以示例树手工推演对第一节的示例树深度为 3递归自底向上的求值过程是叶结点 4、5、3左右子树均为空返回0 1 1结点 21 max(depth(4)1, depth(5)1) 2根结点 11 max(depth(2)2, depth(3)1) 3。最终结果为 3与直接观察最长路径 1 → 2 → 4 的结点计数一致。复杂度分析时间复杂度 O(n)每个结点恰好被访问一次每次只做一个 max 加一次加法共 O(1) 额外工作空间复杂度 O(h)h 为树高即递归栈深度。最坏情况下树退化成单链左斜或右斜h n空间 O(n)平衡树则 h ≈ log n。三、迭代解法用队列逐层计数递归的本质是自底向上算高度如果希望自顶向下求深度可以改用层次遍历——思路与仓库中 32.1 从上往下打印二叉树 里按层控制队列弹出个数的技巧完全一致每一轮从队列中取出一整层的结点深度计数器加 1。public int TreeDepth(TreeNode root) { if (root null) { return 0; } QueueTreeNode queue new LinkedList(); queue.add(root); int depth 0; while (!queue.isEmpty()) { int cnt queue.size(); // 当前层的结点数 depth; while (cnt-- 0) { TreeNode t queue.poll(); if (t.left ! null) queue.add(t.left); if (t.right ! null) queue.add(t.right); } } return depth; }两种方式对比解法遍历方向时间额外空间特点递归后序自底向上O(n)O(h) 递归栈代码最短面试首选队列分层BFS自顶向下O(n)O(w) 最宽层结点数无递归溢出风险天然支持求第 k 层变体对于超深退化的单链表型树BFS 解法可以规避递归栈溢出这是它相对递归解法的实际价值所在。四、进阶深度/高度的自底向上复用——55.2 平衡二叉树求子树高度并自底向上传递是 55.1 提炼出的通用模式仓库下一题 55.2 平衡二叉树 正是它的直接应用。55.2 的题目描述为平衡二叉树左右子树高度差不超过 1其解法在 55.1 的height递归中顺带检查每对左右子树的差值private boolean isBalanced true; public boolean IsBalanced_Solution(TreeNode root) { height(root); return isBalanced; } private int height(TreeNode root) { if (root null || !isBalanced) return 0; int left height(root.left); int right height(root.right); if (Math.abs(left - right) 1) isBalanced false; return 1 Math.max(left, right); }从源码结构看这里有两个值得注意的细节判断与求高合并为一次遍历height既是 55.1 求深度的核心逻辑又顺手完成了平衡性判断整体仍是 O(n)避免了先判平衡再求高度的多次遍历!isBalanced提前剪枝一旦发现某个结点失衡就置标志位之后所有递归分支直接在if处返回 0 不再深入保证最坏情况下的常数开销。这也说明掌握 55.1 的后序递归返回子树高度这一骨架后凡是涉及左右子树高度比较的题目如 55.2都能在同一遍历框架内完成而不需要额外的辅助结构。五、易错点小结与相关题目结合 notes/55.1 二叉树的深度.md 的解法与仓库内其它树题解常见失分点有空树约定深度问题约定空树为 0若题目约定空树高度为 -1部分教材的 height 定义则1 max(...)的写法需同步调整写码前先确认基准深度 vs 层数按本文定义深度是结点数等于最长路径的边数加 1与第几层在数值上恰好一致但表述不同面试回答时要说清楚退化树整棵树只有一条链时深度为 n递归解法此时栈深 O(n)极端输入下应改用 BFS 解法。仓库中与本题模式相关的题解可继续参考对称的二叉树同样是对两棵子树同步递归的模板写法32.1 从上往下打印二叉树队列按层遍历的完整实现BFS 解法的基础二叉树中和为某一值的路径自顶向下递归 回溯的另一类树遍历模式剑指 Offer 题解 - 目录本系列全部 68 题的导航Leetcode 题解 - 树仓库中树专题的更大量练习其中包含与树的最大深度同类的问题。【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考