这道题不仅考察二叉树的遍历更是理解回溯算法Backtracking的绝佳练手题。本文的思路参考了《代码随想录》希望能用最清晰的逻辑和保姆级的代码注释和我一起把这道题彻底拿下一、 题目描述给定一个二叉树的根节点root按任意顺序返回所有从根节点到叶子节点的路径。叶子节点是指没有子节点的节点。示例 1输入root [1,2,3,null,5]输出[1-2-5,1-3]示例 2输入root [1]输出[1]二、思路分析要求出所有从根节点到叶子节点的路径我们要思考三个核心问题用什么遍历方式既然要找“路径”肯定要从根节点顺着往下走所以我们必须采用前序遍历中-左-右。只有先处理父节点中才能把沿途的节点按顺序记录下来。如何记录和收集路径在往下遍历的过程中我们需要用一个结构比如数组或列表path把走过的节点记录下来。当遇到叶子节点即left和right都是空时说明找到了一条完整的到底路径。此时我们将path里的节点按要求拼接成字符串并放入最终的结果集result中。为什么要回溯当我们走到叶子节点记录完一条路径后怎么去走另一条路径呢我们需要退回到上一个分叉口父节点然后再去遍历它的另一棵子树。这个“退回”的过程在代码层面就体现为把path中最后加入的那个节点弹出来。这就是回溯三、代码实现保姆级逐行注释下面提供 C、C 和 Python 三个版本的实现均采用标准的回溯写法每行都加上了详细注释保证小白也能看懂1. C 版本在 C 中我们用vectorint来存储当前的路径path用vectorstring存储最终结果result。这种写法把遍历和回溯的动作分得非常清晰。/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { private: // 递归遍历函数cur代表当前处理的节点path记录当前走过的路径 // result用来存放最终所有的路径字符串 void traversal(TreeNode* cur, vectorint path, vectorstring result) { // 中将当前遍历到的节点的值加入到路径数组 path 中 path.push_back(cur-val); // 判断当前节点是否为叶子节点即左右子节点均为空 if (cur-left NULL cur-right NULL) { string sPath; // 定义一个字符串用于拼接当前收集到的整条路径 // 遍历 path 数组中除了最后一个节点之外的所有节点 for (int i 0; i path.size() - 1; i) { // 将节点值转换为字符串并拼接上 - 箭头 sPath to_string(path[i]) -; } // 拼接最后一个节点的值注意末尾不需要加 - sPath to_string(path[path.size() - 1]); // 将拼接好的整条路径字符串加入到最终的结果集 result 中 result.push_back(sPath); return; // 当前叶子节点处理完毕结束当前层的递归函数返回上一层 } if (cur-left) { // 如果当前节点存在左子节点 // 递归调用向左子树方向继续深度优先遍历 traversal(cur-left, path, result); // 回溯遍历完左子树的路径后需要把刚加进去的左子节点从 path 中弹出 // 以便去遍历右子树 path.pop_back(); } if (cur-right) { // 如果当前节点存在右子节点 // 递归调用向右子树方向继续深度优先遍历 traversal(cur-right, path, result); // 回溯遍历完右子树后同样需要把右子节点弹出恢复到当前节点的状态 path.pop_back(); } } public: vectorstring binaryTreePaths(TreeNode* root) { vectorstring result; // 定义结果集用于保存所有满足条件的路径字符串 vectorint path; // 定义路径数组用于在递归过程中临时记录经过的节点值 if (root NULL) return result; // 如果传入的是一棵空树直接返回空的结果集 traversal(root, path, result); // 从根节点开始调用递归函数进行遍历和路径收集 return result; // 遍历结束后返回最终收集到的所有路径列表 } };2. C 语言版本C 语言处理字符串和动态数组相对麻烦我们需要自己管理内存。巧妙之处在于我们可以通过按值传递记录路径长度的pathLen变量来隐式地完成回溯。/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ #include stdio.h #include stdlib.h // 递归遍历函数cur是当前节点path是记录路径值的数组pathLen是当前路径的节点数result是结果集returnSize记录最终结果集的条数 void traversal(struct TreeNode* cur, int* path, int pathLen, char** result, int* returnSize) { // 中将当前节点的值存入 path 数组同时让记录路径长度的 pathLen 自增 1 path[pathLen] cur-val; // 判断是否到达叶子节点即当前节点的左右孩子都为空 if (cur-left NULL cur-right NULL) { // 为当前完整的路径字符串动态分配内存空间保守假设长度不超过1000 char* str (char*)malloc(sizeof(char) * 1000); int len 0; // 记录当前字符串拼接到的位置偏移量 // 遍历 path 数组中除了最后一个节点外的所有节点 for (int i 0; i pathLen - 1; i) { // 使用 sprintf 将整数和箭头格式化写入字符串并累加返回的字符长度更新偏移量 len sprintf(str len, %d-, path[i]); } // 单独拼接最后一个叶子节点的值不带箭头 sprintf(str len, %d, path[pathLen - 1]); // 将拼好的字符串指针存入结果集数组同时将结果集的总量 returnSize 自增 1 result[(*returnSize)] str; return; // 遇到叶子节点当前支路处理完毕返回上一层 } if (cur-left) { // 如果当前节点左子树不为空 // 递归遍历左子树。 traversal(cur-left, path, pathLen, result, returnSize); } if (cur-right) { // 如果当前节点右子树不为空 // 递归遍历右子树。 traversal(cur-right, path, pathLen, result, returnSize); } } char** binaryTreePaths(struct TreeNode* root, int* returnSize) { *returnSize 0; // 初始化返回的路径总条数为 0 if (root NULL) return NULL; // 如果是一棵空树无路径可找直接返回 NULL // 为结果集二维字符数组分配内存假设最多1000条路径 char** result (char**)malloc(sizeof(char*) * 1000); // 定义一个足够大的局部整型数组用来充当记录当前路径的栈 int path[1000]; // 初始调用递归函数从根节点开始找当前路径长度为 0 traversal(root, path, 0, result, returnSize); // 返回包含所有路径字符串的二维数组指针 return result; }3. Python 版本Python 的列表操作非常灵活我们可以利用append和pop完美复刻 C 的回溯逻辑同时利用join函数极大地简化字符串的拼接过程。# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def binaryTreePaths(self, root: Optional[TreeNode]) - List[str]: result [] # 定义一个空列表 result用来存储所有最终拼接好的路径字符串 path [] # 定义一个空列表 path用来在递归过程中动态充当栈记录经过的每一个节点的值 if not root: # 判断如果根节点为空即传入了一棵空树 return result # 直接返回空的 result 列表 self.traversal(root, path, result) # 从根节点开始调用递归函数进行深度优先遍历 return result # 遍历完成后返回装满完整路径的 result 列表 def traversal(self, cur: TreeNode, path: List[str], result: List[str]): path.append(str(cur.val)) # 中将当前节点的值转换成字符串类型并追加到 path 列表的末尾 # 判断当前节点是否为叶子节点即左子树和右子树都为空 if not cur.left and not cur.right: # 如果是叶子节点说明找到了一条完整的路径。 # 利用 python 字符串的 join 方法以 - 为连接符将 path 列表中的字符串元素高效地拼接起来并加入结果集 result.append(-.join(path)) return # 当前叶子节点处理完毕结束当前递归函数的执行直接返回上一层 if cur.left: # 如果当前节点拥有左子树 self.traversal(cur.left, path, result) # 递归调用自身向左子树继续探索 path.pop() # 回溯左子树的所有路径都探索完毕并返回后将 path 列表最后加入的那个左子节点弹出恢复之前的状态 if cur.right: # 如果当前节点拥有右子树 self.traversal(cur.right, path, result) # 递归调用自身向右子树继续探索 path.pop() # 回溯右子树探索完毕后同样将最后加入的那个右子节点弹出恢复到当前节点原本的状态四、 详细复杂度推导很多同学会背复杂度但不知道怎么推导来的。这里详细说明一下设二叉树的节点总数为 N。1. 时间复杂度O(N^2)大家可能会疑惑为什么遍历全部节点的时间复杂度不是 O(N) 呢遍历节点本身我们确实只对每个节点访问了一次这一部分的耗时是 O(N)。路径拼接的额外开销当遇到叶子节点时我们需要把path数组里的数字拼成字符串。最坏情况分析考虑一种极端形状的二叉树——它长得像一把梳子每一层都有一个叶子节点且整棵树的高度接近 N。此时我们会有 O(N) 个叶子节点且每条路径的长度也接近 O(N)。每次拼接字符串都需要拷贝一遍路径上的所有字符所以总的字符串拷贝时间累加起来会达到 O(N^2) 的量级。结论总时间复杂度由遍历操作和字符串拷贝操作共同决定取最大量级因此为 O(N^2)。2. 空间复杂度O(N)递归调用栈在最坏情况下二叉树退化成一条直线的链表递归深度会达到 N此时系统函数调用栈占用 O(N) 的空间。路径数组/列表path记录当前路径的容器在最坏情况下也需要存储 N 个节点占用 O(N) 的空间。结论两者最大都是 O(N) 级别因此整体空间复杂度为 O(N)。注意通常我们计算空间复杂度时不将返回的最终result数组计算在内只计算辅助空间。C语言硬核小课堂面试加分项在上述 C 语言的代码实现中有两处极其精妙的底层操作如果你能弄懂它们说明你的 C 语言功底已经相当扎实了痛点 1len sprintf(str len, %d-, path[i]);到底在干嘛很多初学者看到这里会发懵str明明是个字符串数组/指针为什么要加上len核心揭秘利用“指针偏移”实现字符串的连续追加。背景sprintf的默认行为是覆盖写入。如果你每次都写sprintf(str, ...)那么新写入的字符永远会从字符串的第 0 个位置开始覆盖导致你最后只能得到最后一个数字。int sprintf(char *str, const char *format, ...)发送格式化输出到str所指向的字符串。拆解str是指向这块内存起始位置索引 0的指针。len记录的是目前为止已经成功写入了多少个字符也就是当前字符串的长度。str len的作用是将“写字的笔尖”向后移动len个字节定位到上一次刚写完的尾巴处。sprintf执行成功后会返回它这一次刚刚写入了几个字符。脑内推演假设path是[1, 2, 5]第一轮 (1)str为空len 0。sprintf(str 0, %d-, 1)从头写入1-返回 3 个字符长度。此时len更新为0 3 3。第二轮 (2)指针向后偏移 3 个字节sprintf(str 3, %d-, 2)接着上一次的尾巴写入2-返回 3。此时len更新为3 3 6。字符串变成了1-2-。总结通过不断累加len并进行指针偏移我们硬生生用sprintf砸出了类似 Java 中StringBuilder.append()的高效追加效果痛点 2path[pathLen] cur-val;为什么能“隐式回溯”在 C 和 Python 的代码中我们每次递归完左子树都需要老老实实地调用pop_back()或pop()把加进去的节点弹出来。为什么 C 语言版本里却没有看到任何pop操作核心揭秘按值传递Pass by Value 覆盖写入。局部变量的魔法在 C 语言的traversal函数参数中pathLen是按值传递的。这意味着每一次进入新的递归层系统都会为当前的pathLen复制一个局部的副本。脑内推演假设当前在节点1准备遍历左孩子2和右孩子3当前层pathLen 1数组里存着[1]。走向左子树调用traversal(cur-left, path, pathLen, ...)。注意传进去的pathLen是1。左子树内部执行path[pathLen] 2。此时数组的第1个位置被填入了2数组变成[1, 2]并且左子树那一层的局部变量pathLen变成了2。左子树递归结束返回当前层神奇的事情发生了因为是按值传递虽然左子树把自己的pathLen变成了2但当前层的pathLen依然是1走向右子树调用traversal(cur-right, path, pathLen, ...)传进去的pathLen依然是1右子树内部执行path[pathLen] 3。此时它会直接把刚才存左孩子2的位置索引1无情覆盖掉数组变成了[1, 3]。总结因为我们用pathLen当作栈顶指针按值传递保证了“返回上一层时栈顶指针自动恢复”。既然栈顶指针恢复了下一次再进栈的新数据就会自然而然地覆盖掉原来由于走错路上一条支路而写下的旧数据。我们根本不需要去擦除pop旧数据只要把指针拨回来新数据直接覆盖上去这就是最高级的隐式回溯结尾感谢卡哥无私奉献精彩的教学视频贴上本题代码随想录的网址257. 二叉树的所有路径 | 代码随想录力扣链接257. 二叉树的所有路径 - 力扣LeetCode