个人主页北极的代码欢迎来访作者简介java后端学习者❄️个人专栏苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺前言大家好我是代码不加冰今天我们来学习二叉树相关的算法题具体是关于二叉树的路径问题其实也就是递归的问题我们后面要学的回溯的实现通常就是使用递归来实现的所以还是很重要的让我们来具体看看吧。摘要本文探讨了二叉树路径问题的递归解法。题目要求返回所有从根节点到叶子节点的路径通过前序遍历和回溯算法实现。核心思路是使用path列表记录当前路径遇到叶子节点时将路径转为字符串存入result递归访问左右子树后通过path.remove()实现回溯。文章详细解析了递归函数各环节的实现逻辑包括路径记录、叶子节点判断、递归调用和回溯操作并提供了完整的Java代码实现。该方法有效解决了二叉树路径遍历问题时间复杂度为O(n)空间复杂度为O(h)其中h为树的高度。题目背景给你一个二叉树的根节点root按任意顺序返回所有从根节点到叶子节点的路径。叶子节点是指没有子节点的节点。示例 1输入root [1,2,3,null,5]输出[1-2-5,1-3]示例 2输入root [1]输出[1]提示树中节点的数目在范围[1, 100]内-100 Node.val 100题目解析根据题目分析并不是简单的遍历问题我们需要返回所有路径因此即便我们走过了之前的节点也要回去看那个节点还有没有别的路径这叫回溯听着挺高大上的其实就是跟开车差不多在一个路口有多条路我们在路口这个节点可以选择一个但是之后还要回到路口把剩下的路一条条的走完。核心要点要点说明遍历方式前序遍历根 → 左 → 右何时记录遇到叶子节点左右都为空何时回溯离开当前节点时从路径中删除它路径表示用ListString或StringBuilder维护具体的实现例子需要注意前进负责加节点、构建路径回溯负责删节点、清理现场路径是维护在一个全局或传参的列表里的回溯删除的是当前节点根节点不会被删除除非整个递归全部结束根节点一直保留是因为还没从根节点回溯回去我们回溯每次只回到上一个节点但是题目要求返回的是从根节点到所有子节点的完整路径对于一开始刚学回溯的同学来说可能容易混淆错误的认为回溯是回到第一个节点然后从头开始如果真是这样可能会导致后面的路径丢失遍历不完整个树。理解认为回溯后果❌ 错误回到根节点从头开始路径永远只有一条永远走不完所有组合✅ 正确回到上一个节点继续尝试路径逐步构建、撤销覆盖所有可能性理解完这些那么这题就很简单了仅仅是代码实现的问题了。在二叉树路径问题中通常有两个容器容器作用存储内容示例result存储最终结果所有路径字符串[1-2-5, 1-3]path存储当前正在走的路径当前路径的节点值[1,2,5]path是临时工不断变化记录当前走到哪了不断变化回溯删除result是永久存储一旦记录一条完整路径就永久保存第1段主方法javapublic ListString binaryTreePaths(TreeNode root) { ListString result new ArrayList(); if (root null) return result; ListInteger path new ArrayList(); dfs(root, path, result); return result; }解释result最终要返回的结果装所有路径字符串如果树是空的直接返回空列表题目要求path临时记录当前走的路径比如[1,2,5]调用dfs开始深度优先搜索第2段递归函数开头——做选择javaprivate void dfs(TreeNode node, ListInteger path, ListString result) { path.add(node.val);解释每进入一个节点就把它的值加入path例如从节点1进入节点2path从[1]变成[1,2]这就是“做选择”——把当前节点纳入当前路径第3段叶子节点判断javaif (node.left null node.right null) { result.add(buildPath(path)); }解释如果当前节点没有左孩子也没有右孩子 → 说明是叶子节点一条完整的路径已经形成从根到当前叶子调用buildPath把[1,2,5]转成1-2-5加入result示例走到节点5时path [1,2,5]记录下1-2-5第4段非叶子节点——继续递归javaelse { if (node.left ! null) dfs(node.left, path, result); if (node.right ! null) dfs(node.right, path, result); }解释如果不是叶子说明还可以往下走有左孩子就递归左子树有右孩子就递归右子树注意递归完成后会回到这里继续往下执行第5段回溯——撤销选择javapath.remove(path.size() - 1);解释这是最容易被忽略的一行当前节点的左右子树都探索完了要离开这个节点离开之前必须把它从path中删除这样返回上一层时path还是原来的样子示例进入5之前path [1,2]进入5path [1,2,5]记录完路径离开5path [1,2]← 恢复原样这样节点2才能继续去探索其他孩子第6段格式化方法javaprivate String buildPath(ListInteger path) { StringBuilder sb new StringBuilder(); for (int i 0; i path.size(); i) { if (i 0) sb.append(-); sb.append(path.get(i)); } return sb.toString(); }解释把[1,2,5]转成1-2-5用StringBuilder效率更高if (i 0)确保第一个数字前面不加-题目答案/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { public ListString binaryTreePaths(TreeNode root) { ListString resultnew ArrayList(); if(rootnull){ return result;} ListInteger pathnew ArrayList(); dfs(root, path, result); return result; } private void dfs(TreeNode node,ListIntegerpath,ListString result){ path.add(node.val); if (node.left null node.right null) { result.add(buildPath(path)); } else { // 3. 继续递归探索子节点 if (node.left ! null) dfs(node.left, path, result); if (node.right ! null) dfs(node.right, path, result); } path.remove(path.size() - 1); } private String buildPath(ListInteger path){ StringBuilder sbnew StringBuilder(); for(int i0;ipath.size();i){ if(i0) sb.append(-); sb.append(path.get(i)); } return sb.toString(); } }结语如果对你有帮助请点赞关注收藏你的支持就是我最大的鼓励