leetcode 257. 二叉树的所有路径-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode 257. 二叉树的所有路径。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

2023.7.5

leetcode 257. 二叉树的所有路径,leetcode专栏,leetcode,算法,c++,数据结构

这题需要用到递归+回溯，也是我第一次接触回溯这个概念。

大致思路是：

在reversal函数中，首先将当前节点的值加入到路径path中。然后判断当前节点是否为叶子节点，即没有左右子节点。如果是叶子节点，将路径转化为字符串并保存到result中。

接下来，分别递归处理当前节点的左子节点和右子节点。递归调用reversal函数时，将左子节点或右子节点作为新的当前节点，并传递更新后的路径path和result。在递归调用之后，需要进行回溯操作，即将刚添加的节点值从路径path中移除，以保证在遍历其他路径时路径的正确性。

总体而言，通过递归的深度优先搜索算法，遍历了给定二叉树的所有路径，并将路径保存在一个字符串的向量中。下面上代码：

class Solution {
public:
    void reversal(TreeNode* cur, vector<int>& path, vector<string>& result)
          {
              path.push_back(cur->val);
              if(cur->left==nullptr && cur->right==nullptr) //叶子节点 将路径保存
              {
                  string spath;
                  for(int i=0; i<path.size()-1; i++)
                  {
                      spath += to_string(path[i]); //需要将数组的整型值->字符串型值
                      spath += "->";
                  }
                  spath += to_string(path[path.size()-1]);
                  result.push_back(spath);
              }
              if(cur->left)
              {
                  reversal(cur->left,path,result);
                  path.pop_back();//回溯
              }
              if(cur->right)
              {
                  reversal(cur->right,path,result);
                  path.pop_back();//回溯
              }
          }

    vector<string> binaryTreePaths(TreeNode* root) {
          vector<string> result;
          vector<int> path;
          reversal(root, path, result);
          return result;
    }
};

需要注意reversal函数传递参数的两个vector 需要加&符号，以保证是在原vector上修改。文章来源地址https://www.toymoban.com/news/detail-521928.html

到了这里，关于leetcode 257. 二叉树的所有路径的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！