深搜(二叉树的所有路径)(6)

https://blog.csdn.net/2601_95366422/article/details/159251855

一.题目

257. 二叉树的所有路径 - 力扣（LeetCode）

二.思路讲解

2.1 选择遍历方式

本题要求返回从根节点到所有叶子节点的路径，因此我们需要采用前序遍历，这样才能在访问节点时从根开始逐步向下构建路径。前序遍历的顺序是根-左-右，正好符合路径的生成顺序。

2.2 路径的构建与存储

在遍历过程中，我们需要一个数据结构来记录当前路径。通常使用一个字符串path来存储从根到当前节点的路径表示。对于普通节点，我们应将节点值转换为字符串，并加上"->"作为分隔；而对于叶子节点，则只需加上节点值即可，然后将完整路径存入结果数组ret中。这里，path和ret可以是全局变量或通过参数传递。

2.3 回溯与参数传递的权衡

如果采用全局变量path，那么在递归返回时，需要手动恢复现场（即删除刚刚添加的节点部分），否则路径会错误累积。例如，处理完一个叶子节点后，必须将最后添加的节点值及箭头弹出，以便后续路径使用。这种回溯操作容易遗漏，导致错误。

如果将path作为递归函数的参数传递，则每次递归调用都会创建一个新的字符串副本，无需手动恢复现场，因为参数是值传递，不会影响上一层的path。这种方式更安全。

2.4 递归终止条件与剪枝

为了简化问题，我们将叶子节点作为递归的最简单情况。当遇到叶子节点时，直接构建完整路径并存入结果，然后返回，不再继续递归。这样，我们就不需要递归到空节点，从而剪枝掉空节点的判断，使代码更简洁高效。具体来说，在递归函数中，首先处理当前节点，如果当前节点是叶子节点，则记录路径并返回；否则，分别递归左子树和右子树（如果存在）。这样，我们通过提前终止避免了不必要的空节点递归。

三.代码演示

/** * 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 { public: vector<string> ret; vector<string> binaryTreePaths(TreeNode* root) { string path = ""; dfs(root,path); return ret; } void dfs(TreeNode* root,string path) { //1.是叶子节点 if(root->left == nullptr && root->right == nullptr) { path += to_string(root->val); ret.push_back(path); return; } //2.不是叶子节点 path += to_string(root->val); path += "->"; if(root -> left != nullptr) dfs(root->left,path); if(root -> right != nullptr) dfs(root->right,path); } };

四.代码演示

一、递归函数设计

我们定义一个递归函数dfs(TreeNode* root, string path)，它的作用是：以当前节点root为起点，从根到该节点的路径已经记录在path中，继续向下遍历，并将所有从根到叶子节点的完整路径存入结果数组ret。这里path采用值传递，这样每一层递归都有自己的副本，无需手动回溯。

二、递归终止条件（叶子节点处理）

本题将叶子节点作为递归的最简单情况。当当前节点的左右子节点均为空时，说明到达叶子节点。此时，我们将当前节点的值追加到path中，形成完整路径，然后将其加入结果数组ret，并返回。这样，我们无需递归到空节点，避免了不必要的递归调用，实现了剪枝。

三、递归步骤分解（非叶子节点处理）

对于非叶子节点，我们需要继续向下遍历左右子树。步骤如下：

1. 构建当前路径：将当前节点的值转换为字符串，并加上"->"分隔符，追加到path末尾。

2. 递归左子树：如果左孩子存在，调用dfs(root->left, path)，传入更新后的路径。

3. 递归右子树：如果右孩子存在，调用dfs(root->right, path)。

注意，由于path是值传递，左右子树的递归调用使用的是不同的副本，因此不会相互干扰，也无需手动恢复现场。

四、参数传递与回溯

这里采用path作为函数参数（值传递），而不是全局变量。这样做的好处是：

• 每次递归调用都会创建新的字符串副本，自动隔离不同分支的路径。

• 避免了手动回溯（如pop_back）的麻烦，降低了出错概率。

• 虽然会产生一定的拷贝开销，但路径长度有限，完全可以接受。

如果使用全局变量，则需要在每次递归返回后手动删除刚刚添加的部分，这容易遗漏，而参数传递则天然解决了这个问题。

五、关键细节

• 叶子节点的判断：直接检查root->left == nullptr && root->right == nullptr，因为题目保证每个节点要么有孩子要么没有。

• 路径构建：对于非叶子节点，需要添加"->"；对于叶子节点，只添加节点值，不加箭头。

• 空节点剪枝：在递归前先判断孩子是否存在，避免了调用空节点，进一步优化。

• 结果数组：ret作为成员变量，在递归过程中不断添加完整路径。