二叉树‘找叶子’的三种姿势：从PTA真题到LeetCode变体（层次/先序/后序遍历对比）

二叉树‘找叶子’的三种姿势从PTA真题到LeetCode变体层次/先序/后序遍历对比在算法学习的道路上二叉树遍历是每个程序员必须掌握的基本功。而找叶子节点这一看似简单的任务却能衍生出多种解法每种解法背后都隐藏着不同的算法思维。本文将带您深入探索层次遍历、先序遍历和后序遍历在解决叶子节点问题上的独特表现并通过PTA真题与LeetCode变体的对比展示如何将一种解法迁移到多种场景。1. 理解问题本质什么是叶子节点在二叉树中叶子节点是指没有子节点的末端节点。识别叶子节点是许多算法问题的基础比如计算树的高度、统计节点数量或进行特定类型的搜索。理解叶子节点的定义看似简单但在实际应用中却可能遇到各种变体普通叶子节点左右子节点均为空的节点左叶子节点作为父节点左子节点的叶子节点右叶子节点作为父节点右子节点的叶子节点特定深度叶子节点位于树中特定层次的叶子节点// 判断是否为叶子节点的基本代码 int isLeaf(TreeNode* node) { return node ! NULL node-left NULL node-right NULL; }2. 层次遍历法按层级收集叶子节点层次遍历BFS是解决PTA原题列出叶结点最直观的方法因为它天然符合题目要求的从上到下、从左到右的输出顺序。2.1 基本实现思路使用队列辅助进行遍历从根节点开始将节点入队每次从队列中取出节点进行检查如果是叶子节点则记录将非空子节点入队def level_order_leaves(root): if not root: return [] queue [root] leaves [] while queue: node queue.pop(0) if not node.left and not node.right: leaves.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) return leaves2.2 复杂度分析指标值说明时间复杂度O(n)需要访问所有节点空间复杂度O(w)w为树的最大宽度适用场景需要层级信息如按层统计或特定层叶子节点提示层次遍历特别适合需要保持节点顺序的场景如PTA原题要求的输出顺序。3. 先序遍历法深度优先的叶子收集先序遍历根-左-右虽然不能直接保证节点的层级顺序但在某些场景下更为灵活特别是当需要结合其他条件筛选叶子节点时。3.1 递归实现ListInteger preorderLeaves(TreeNode root) { ListInteger leaves new ArrayList(); preorderHelper(root, leaves); return leaves; } void preorderHelper(TreeNode node, ListInteger leaves) { if (node null) return; if (node.left null node.right null) { leaves.add(node.val); } preorderHelper(node.left, leaves); preorderHelper(node.right, leaves); }3.2 迭代实现def preorder_leaves(root): if not root: return [] stack [root] leaves [] while stack: node stack.pop() if not node.left and not node.right: leaves.append(node.val) # 注意入栈顺序先右后左 if node.right: stack.append(node.right) if node.left: stack.append(node.left) return leaves4. 后序遍历法从底部向上的视角后序遍历左-右-根在处理叶子节点时有其独特优势特别是在需要先处理子节点再处理父节点的场景中。4.1 经典应用计算叶子节点之和function postorderSum(root) { if (!root) return 0; let leftSum postorderSum(root.left); let rightSum postorderSum(root.right); if (!root.left !root.right) { return root.val; } return leftSum rightSum; }4.2 与先序遍历的对比特性先序遍历后序遍历访问顺序根-左-右左-右-根叶子处理时机首次遇到时所有子节点处理完后适用场景需要尽早筛选叶子节点需要子节点信息处理父节点5. 从PTA到LeetCode算法思维的迁移掌握了基本方法后我们可以将这些技巧应用到更复杂的问题中。以下是几个LeetCode上的变体问题5.1 找左叶子节点LeetCode 404int sumOfLeftLeaves(TreeNode* root) { if (!root) return 0; int sum 0; if (root-left !root-left-left !root-left-right) { sum root-left-val; } return sum sumOfLeftLeaves(root-left) sumOfLeftLeaves(root-right); }5.2 统计特定深度叶子节点LeetCode 366def findLeaves(root): result [] def dfs(node): if not node: return -1 left_depth dfs(node.left) right_depth dfs(node.right) current_depth max(left_depth, right_depth) 1 if current_depth len(result): result.append([]) result[current_depth].append(node.val) return current_depth dfs(root) return result6. 性能对比与选择策略不同的遍历方法在不同场景下各有优劣。以下是三种方法的多维度对比指标层次遍历先序遍历后序遍历顺序保持优秀一般一般空间效率中等优秀优秀实现复杂度中等简单中等适用问题范围特定顺序灵活筛选需要子节点信息在实际项目中我通常会根据以下因素选择方法如果需要保持层级顺序优先考虑层次遍历如果只需要收集叶子节点而不关心顺序先序遍历通常最简单如果需要基于子节点信息做决策后序遍历是更好的选择