题目

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

示例 1：
image.png

  1. 输入：root = [1,2,3,null,5]
  2. 输出：["1->2->5","1->3"]

示例 2：

  1. 输入：root = [1]
  2. 输出：["1"]

提示：

  • 树中节点的数目在范围 [1, 100] 内

  • -100 <= Node.val <= 100

    解题方法

    递归（DFS）

    通过递归遍历二叉树，在递归过程中记录路线，到达叶节点后将路线压入结果数组。
    时间复杂度O(n^2)（变量拷贝耗时O(n)），空间复杂度O(n^2)
    C++代码：

    /**
* 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:
  void search(TreeNode* cur, string s, vector<string>& result){
      if(!cur) return;
      s += to_string(cur->val);
      if(!cur->left && !cur->right)   result.push_back(s);
      search(cur->left, s+"->", result);
      search(cur->right, s+"->", result);
  }

  vector<string> binaryTreePaths(TreeNode* root) {
      vector<string> result;
      string s = "";
      search(root, s, result);

      return result;
  }
};

    迭代（BFS）

    通过迭代 BFS 遍历二叉树，使用队列同时记录节点以及当前路径。
    时间复杂度O(n^2)，空间复杂度O(n^2)
    C++代码：

    /**
* 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> binaryTreePaths(TreeNode* root) {
      vector<string> result;
      if(!root)   return result;
      queue<TreeNode*> nodes;
      queue<string> paths;
      nodes.push(root);
      paths.push(to_string(root->val));
      while(nodes.size()>0) {
          TreeNode* cur = nodes.front(); nodes.pop();
          string cur_path = paths.front(); paths.pop();
          if(!cur->left && !cur->right)   result.push_back(cur_path);
          if(cur->left) {
              paths.push(cur_path+"->"+to_string(cur->left->val));
              nodes.push(cur->left);
          }
          if(cur->right) {
              paths.push(cur_path+"->"+to_string(cur->right->val));
              nodes.push(cur->right);
          }
      }

      return result;
  }
};