本文共 1523 字，大约阅读时间需要 5 分钟。

二叉树路径收集问题是一个常见的二叉树遍历问题。问题的核心是对于二叉树中的每个节点，收集从根节点到该节点的路径，并将这些路径返回。传统的方法通常使用深度优先搜索（DFS），这种方法遍历树结构，记录路径信息。

方法一：递归实现

递归实现是理解这个问题的最直接方式。在递归DFS中，我们可以将路径信息用一种临时变量来保存。具体来说，对于每一个节点，我们将其值添加到临时路径中，然后递归处理左子树和右子树。这个时候值需要通过“路径 threadIdx”来保持线索。当到达叶子节点时，临时路径被正式添加到结果列表中。

这种方法的代码实现简单直观，但是递归实现可能引发栈溢出问题（尤其是非常大的树或者高度为很大的树）。因此，在实际应用中，需要对树的高度和规模有所了解，避免因栈深度过大的问题。

方法二：迭代实现

为了避免栈溢出的问题，可以将递归的DFS转化为迭代的DFS。这种方法的缺点是实现稍微复杂一些，需要模拟栈结构来保存路径信息。不过，迭代实现会显著提高树的高度的处理能力，适用于大规模树结构。

在迭代实现中，我们使用一个“栈”结构，将节点的信息记录下来。当到达叶子节点时，我们将临时路径合并到最终结果中。这样操作的具体细节需要对栈的遍历方式和路径拼接逻辑进行严格控制。

方法选择

对于一般的问题，对于小型到中型树的处理，递归实现更为高效和简洁。虽然在某些情况下可能存在栈溢出的问题，但通过预先判断树的高度或者使用-safe stack-机制，可以有效性降低问题发生的概率。如果预计处理的树非常大或者高度很高，则迭代实现是更优的选择。

实现代码示例

#include 
   
    #include 
    
     using namespace std;struct TreeNode {    int val;    TreeNode* left = nullptr;    TreeNode* right = nullptr;};vector
     
       binaryTreePaths(TreeNode* root) {    vector
      
        res;    if (root == nullptr) return res;    vector
       
         tmp;    dfs(root, tmp, res);    return res;}void dfs(TreeNode* node, vector
        
         & tmp, vector
         
          & res) { if (node->left == nullptr && node->right == nullptr) { string str; for (int i = 0; i < tmp.size(); ++i) { str += to_string(tmp[i]) + "->"; } str += to_string(node->val); res.push_back(str); return; } tmp.push_back(node->val); dfs(node->left, tmp, res); dfs(node->right, tmp, res); tmp.pop_back();}
         
        
       
      
     
    
   

总结

对于二叉树路径收集问题，选择哪种方法更多取决于应用场景。如果树的高度有限且规模不大，使用递归实现会更简单高效。反之，如果需要处理大规模或者高度较高的树，迭代实现更为稳妥。