LT简单题257-二叉树的所有路径

题目描述：

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

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

示例 1：

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

示例 2：

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

方法一：深度优先搜索（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 construct_paths(TreeNode* root, string path, vector<string>& paths){ //方法一：深度优先搜索

if(root != nullptr){

path += to_string(root->val);

if(root->left == nullptr && root->right == nullptr){ //当前节点是叶子节点

paths.push_back(path);

}else{ //当前节点不是叶子节点

path += "->";

construct_paths(root->left, path, paths);

construct_paths(root->right, path, paths);

}

}

}

vector<string> binaryTreePaths(TreeNode* root) {

vector<string> paths;

construct_paths(root, "", paths);

return paths;

}

};

时间复杂度：O（N²），空间复杂度：O（N²），其中 N 表示节点数目。