1 DFS
代码语言：javascript复制/**
* 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 dfs(TreeNode* root, vector<string>& path, string str) {
if (!root) return;
if (!root->left && !root->right) {
str = to_string( root->val );
path.push_back(str);
return;
}
str = to_string( root->val ) "->";
dfs(root->left, path, str);
dfs(root->right, path, str);
}
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> path;
dfs(root, path, "");
return path;
}
};
2 BFS
这块其实要多维护一个记录每个节点下累计路径的队列，该队列和数的广度优先队列同步进出数据，当遇到叶节点时，原路径向量把当前叶节点对应的累计路径进行存储即可。
代码语言：javascript复制class Solution {
public:
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> paths_vec;
if (!root) return paths_vec;
queue<TreeNode*> q_tree;
queue<string> q_path;
q_tree.push(root);
q_path.push( to_string(root->val) );
while (!q_tree.empty()) {
TreeNode* node = q_tree.front(); q_tree.pop();
string path = q_path.front(); q_path.pop();
if (!node->left && !node->right)
paths_vec.push_back(path);
else {
if (node->left) {
q_tree.push(node->left);
q_path.push( path "->" to_string(node->left->val) );
}
if (node->right) {
q_tree.push(node->right);
q_path.push( path "->" to_string(node->right->val) );
}
}
}
return paths_vec;
}
};
