二叉树算法中篇：展开·右视图·第K小 —— 递归解题的三种武器

文章目录二叉树算法中篇展开·右视图·第K小 —— 递归解题的三种武器 带你看五道leetcode题前言一、递归心法三道必问二、LC 114 二叉树展开为链表2.1 题目回顾2.2 你的递归解法保存右子树拼接2.3 性能分析while 循环的代价2.4 优化让递归返回尾节点2.5 另一种思路反向先序遍历2.6 小节的空值总结三、LC 199 二叉树的右视图3.1 题目回顾3.2 解法一BFS 层序遍历3.3 解法二DFS 根→右→左3.4 两种方法对比3.5 常见误区四、LC 230 二叉搜索树中第K小的元素4.1 前置知识BST 中序递增4.2 解法一递归中序 计数器4.3 解法二迭代栈完全提前终止4.4 进阶节点计数法适合频繁查询4.5 方法对比五、总结三道题三种递归模式递归模板对比最后的话二叉树算法中篇展开·右视图·第K小 —— 递归解题的三种武器 带你看五道leetcode题前言在[上篇]我们搞定了二叉树的四种遍历前序、中序、后序、层序它们是所有树算法题的地基。中篇我们拿三道高频题来练手每道题都代表一种经典的递归思维模式题目难度核心思维LC 114二叉树展开为链表中等递归 嫁接把子树处理好再拼起来LC 199二叉树的右视图中等DFS 变序遍历 / BFS 层序取末LC 230BST第K小元素中等BST中序递增遍历到第K个停下三道题都不难但每道题的递归写法里都藏着空值陷阱——判了null不等于万事大吉。一、递归心法三道必问写递归之前我给自己定了三问来自我的空值陷阱笔记判了 null就要判空容器用了下标/切片就要判边界越界。对二叉树来说这三问是第一问root null ← 所有人都会写 第二问root.left null ← 你需要 left 做什么它为空能行吗 第三问root.right null ← 你需要 right 做什么它为空能行吗每道题我都会标注最容易被忽略的那一问。下面进入正题。二、LC 114 二叉树展开为链表2.1 题目回顾给你根节点root将二叉树原地展开为一个单链表展开后的顺序为先序遍历根→左→右用right指针作为链表next所有left指针置为null输入: 输出: 1 1 / \ \ 2 5 2 / \ \ \ 3 4 6 3 \ 4 \ 5 \ 62.2 你的递归解法保存右子树拼接这是我最初写的版本classSolution{publicvoidflatten(TreeNoderoot){if(rootnull)return;// ①TreeNoderightroot.right;// ② 保存右子树flatten(root.left);// ③ 展平左子树root.rightroot.left;// ④ 左链 → 右链root.leftnull;// ⑤ 清空 leftflatten(right);// ⑥ 展平保存的右子树while(root.right!null){// ⑦ 走到当前链的末端rootroot.right;}root.rightright;// ⑧ 接上展平后的右子树}}思路拆解用例子走一遍初始: 1 / \ 2 5 / \ \ 3 4 6 Step 1: root1, right5 (保存), flatten(2) Step 2: root2, right4 (保存), flatten(3) Step 3: root3, 左右皆空 → return root.right3, root.leftnull, flatten(4) → return while: 2→3 走到末端(root3), root.right4 结果: 2→3→4 Step 1 继续: root.right2, root.leftnull, flatten(5) Step 5: root5, right6, flatten(null), root.rightnull, flatten(6)→return while: 5.rightnull, root.right6 结果: 5→6 Step 1 继续: while: 1→2→3→4 走到末端(root4), root.right5 最终: 1→2→3→4→5→6 ✅逻辑完全正确但这种写法有一个隐藏的性能问题。2.3 性能分析while 循环的代价while(root.right!null){// ← 这行是 O(n)rootroot.right;}每层递归都要从头走到尾。考虑一棵极度左倾的树1 / 2 / 3处理节点 3走 0 步处理节点 2走 1 步2→3处理节点 1走 2 步1→2→3总步数0 1 2 3即O(n²)最坏情况对于一棵退化成链表的树这个 while 循环会让整体复杂度退化到 O(n²)。2.4 优化让递归返回尾节点思路每次flatten不仅展开子树还返回展开后的尾节点。这样拼接时不需要 while 遍历直接tail.right right。classSolution{publicvoidflatten(TreeNoderoot){flattenAndReturnTail(root);}// 展开以 root 为根的树返回展开后链表的尾节点privateTreeNodeflattenAndReturnTail(TreeNoderoot){if(rootnull)returnnull;// ① null 判空TreeNodeleftTailflattenAndReturnTail(root.left);// ② 展平左子树得到左尾TreeNoderightTailflattenAndReturnTail(root.right);// ③ 展平右子树得到右尾if(leftTail!null){// ④ 判左是否为空leftTail.rightroot.right;// ⑤ 左尾 → 原右子树的头root.rightroot.left;// ⑥ 左链 → 右链root.leftnull;// ⑦ 清空 left}// ⑧ 返回当前链的尾节点右尾 左尾 root 本身if(rightTail!null)returnrightTail;if(leftTail!null)returnleftTail;returnroot;}} 空值陷阱注意第 ④ 行只判root null不够必须判leftTail ! null。因为1 \ 2 root1, leftTailnull, rightTail2 如果直接 leftTail.right root.right → NPE这就是三问中第二问的典型场景你需要leftTail做事但它可能是 null。复杂度时间 O(n)空间 O(h)。每次递归 O(1) 操作不再有 while 遍历。2.5 另一种思路反向先序遍历更简洁的写法——从右往左处理维护一个prev指针classSolution{privateTreeNodeprevnull;publicvoidflatten(TreeNoderoot){if(rootnull)return;// 反向前序右 → 左 → 根flatten(root.right);flatten(root.left);root.rightprev;root.leftnull;prevroot;}}这个写法的妙处在于从链尾往回搭每次处理时prev已经是处理好的后面那段直接接上就行。时间 O(n)空间 O(h)。2.6 小节的空值总结写法最容易漏的判空后果你的版本root.right ! null的 while 条件还好while 条件天然防了返回尾节点版leftTail ! nullNPE反向前序版prev初始为 null第一次root.right null✅无问题三、LC 199 二叉树的右视图3.1 题目回顾给定二叉树根节点返回从右侧能看到的所有节点值从上到下。输入: [1,2,3,null,5,null,4] 1 ← 看到 1 / \ 2 3 ← 看到 32 被 3 挡住 \ \ 5 4 ← 看到 45 被 4 挡住不对... 输出: [1, 3, 4]等等再仔细看5 在深度 24 在深度 2。从右边看4 在 3 的右子5 在 2 的右子。每层取最右的节点所以深度 2 能看到的是 4因为 4 更靠右。3.2 解法一BFS 层序遍历最直观的想法——层序遍历取每层最后一个节点classSolution{publicListIntegerrightSideView(TreeNoderoot){ListIntegerresnewArrayList();if(rootnull)returnres;// ① 判 nullQueueTreeNodequeuenewLinkedList();queue.offer(root);while(!queue.isEmpty()){intsizequeue.size();// ② 当前层节点数for(inti0;isize;i){TreeNodenodequeue.poll();if(isize-1){// ③ 最后一个 最右res.add(node.val);}if(node.left!null)queue.offer(node.left);if(node.right!null)queue.offer(node.right);}}returnres;}}变体写法——先入右子再入左子这样每层第一个出队的就是最右节点// 先右后左入队if(node.right!null)queue.offer(node.right);if(node.left!null)queue.offer(node.left);if(i0)res.add(node.val);// 第一个即最右复杂度时间 O(n)空间 O(w)w 为树的最大宽度。3.3 解法二DFS 根→右→左更优雅的写法——变种先序遍历根 → 右 → 左。核心 trickdepth res.size()意味着当前层第一次被访问由于我们先走右边第一次访问到的就是最右节点。classSolution{publicListIntegerrightSideView(TreeNoderoot){ListIntegerresnewArrayList();dfs(root,res,0);returnres;}privatevoiddfs(TreeNodenode,ListIntegerres,intdepth){if(nodenull)return;// ① 判 nullif(depthres.size()){// ② 关键判断res.add(node.val);// 该层首次访问 → 加入结果}dfs(node.right,res,depth1);// ③ 先右dfs(node.left,res,depth1);// ④ 后左}}图解这个 trick1 depth0, res.size()0 → 加入 1, res[1] / \ 2 3 depth1, res.size()1 → 加入 3先走右边, res[1,3] \ \ 5 4 depth2, res.size()2 → 加入 4先走右边, res[1,3,4] / 6 depth3, res.size()3 → 加入 6, res[1,3,4,6]如果改成先左后右就变成了左视图dfs(node.left,res,depth1);// 先左dfs(node.right,res,depth1);// 后右// → 左视图3.4 两种方法对比BFS 层序DFS 递归时间O(n)O(n)空间O(w) 队列O(h) 递归栈优势直观按层思考代码简洁可改左右顺序变左视图劣势宽树空间大深树可能栈溢出3.5 常见误区❌ 错误想法只走右子树// 错误右子树比左子树短时深层的左子节点也从右侧可见publicvoiddfs(TreeNoderoot){if(rootnull)return;res.add(root.val);dfs(root.right);// 只走右边 → 漏掉深层左子节点}比如这棵树只走右边会漏掉节点 51 / 2 / 5 ← 深度 2 只有左子节点从右边能看到它四、LC 230 二叉搜索树中第K小的元素4.1 前置知识BST 中序递增BST 的定义左子树所有节点 根 右子树所有节点。中序遍历左→根→右遍历 BST 得到的是严格递增序列。这是解 BST 题目的核心武器。验证上一篇文章讲过这里不再展开。如果你需要复习 BST 中序遍历的完整推导见中篇开头提到的验证 BST 的笔记。4.2 解法一递归中序 计数器最直接的思路中序遍历数到第 K 个就停下。classSolution{privateintcount0;privateintresult0;publicintkthSmallest(TreeNoderoot,intk){inorder(root,k);returnresult;}privatevoidinorder(TreeNodenode,intk){if(nodenull)return;// ① 判 nullinorder(node.left,k);// ② 左count;// ③ 根计数if(countk){// ④ 找到第 K 个resultnode.val;return;// 提前终止}inorder(node.right,k);// ⑤ 右}}注意return只是跳出当前层不会终止已经在递归栈中的上层调用。实际上这版代码即使找到后还会继续遍历一些节点。要真正做到找到即停可以加一个判断privatevoidinorder(TreeNodenode,intk){if(nodenull)return;inorder(node.left,k);count;if(countk){resultnode.val;return;}if(countk){// ← 加这行inorder(node.right,k);// 只有还没找到时才继续}}复杂度时间 O(H k)空间 O(H)。H 是树高。4.3 解法二迭代栈完全提前终止递归版的return不能彻底跳出——递归栈里还有父节点等着执行。用显式栈可以做到真正的提前终止classSolution{publicintkthSmallest(TreeNoderoot,intk){DequeTreeNodestacknewArrayDeque();TreeNodecurrroot;while(curr!null||!stack.isEmpty()){// 一路向左全部压栈while(curr!null){stack.push(curr);currcurr.left;}// 弹出栈顶 当前中序节点currstack.pop();k--;if(k0)returncurr.val;// 找到// 转向右子树currcurr.right;}return-1;// 不会执行到这里题目保证 k 有效}} 空值陷阱curr ! null || !stack.isEmpty()这个条件——当curr走到 null 且栈为空时才结束。只判curr ! null会漏掉叶子节点的右子树处理。4.4 进阶节点计数法适合频繁查询如果题目追问“树经常被修改插入/删除且需要频繁查询第 K 小怎么办”思路给每个节点增加一个leftCount字段记录左子树的节点数。如果 k leftCount 1 → 当前节点就是答案 如果 k leftCount → 答案在左子树递归 如果 k leftCount 1 → 答案在右子树k k - leftCount - 1classSolution{publicintkthSmallest(TreeNoderoot,intk){intleftCountcountNodes(root.left);// 左子树节点数if(kleftCount1){returnroot.val;// 根就是答案}elseif(kleftCount){returnkthSmallest(root.left,k);// 在左子树}else{returnkthSmallest(root.right,k-leftCount-1);// 在右子树}}privateintcountNodes(TreeNodenode){if(nodenull)return0;return1countNodes(node.left)countNodes(node.right);}}平衡树时每次查询 O(log n)但如果树退化成链表且无缓存每次countNodes都是 O(n)总复杂度 O(n²)。生产环境中会给节点增加size字段并在插入/删除时维护。4.5 方法对比方法时间空间适合场景递归中序 计数O(Hk)O(H)单次查询代码最简洁迭代栈O(Hk)O(H)单次查询真正提前终止节点计数法O(H) 有缓存, O(N²) 无缓存O(H)频繁查询 树不常变五、总结三道题三种递归模式题目递归模式关键操作最容易漏的判空LC 114展开链表后序拼接先处理好左右再拼接获取尾节点 / 维护 prevleftTail ! null才拼接LC 199右视图变序DFS根→右→左depth 判断depth res.size()首次访问root null返回空列表LC 230第K小中序 计数利用 BST 递增性质计数器到 K 提前停迭代版curr ! null || !stack.isEmpty()递归模板对比LC 114后序拼接: dfs(root): if root null: return 处理左子树 → 得到结果A 处理右子树 → 得到结果B 用 A 和 B 拼接当前层结果 return 当前层结果 LC 199变序DFS: dfs(root, depth): if root null: return if depth res.size(): 加入结果 ← 先序位置 dfs(right, depth1) ← 先右 dfs(left, depth1) ← 后左 LC 230中序 计数: dfs(root): if root null: return dfs(left) ← 左 处理当前节点计数/判断 ← 中序位置 dfs(right) ← 右最后的话三道题都不难但我写递归时每次都会问自己null 判了没有空的判了没有leftTail 为 null、队列为空、栈为空到头了没有k 减到 0、depth 超出范围判了 null不等于万事大吉。真正让你调试半小时的往往是leftTail ! null这种看起来没事的判断。下篇预告二叉树算法下篇——最近公共祖先、路径和、序列化与反序列化。敬请期待。本文是二叉树算法系列的中篇上篇讲解了二叉树的四种遍历方式及其递归/迭代实现。