1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
| /**
* 2019:10:28不在更新日期
* leetcode-cn-257
* icenaive
*/
/**
* 2019:10:28不在更新日期
* leetcode-cn-236
* icenaive
*/
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
// 递归实现
// 使用string 保存路径，当节点不为空是存入当前路径，当节点为叶子节点时，将当前路径保存为答案
// 递归左子树和右子树
// 节点空 返回
// path传值需要赋值传入 否则需要回溯
// ans 需要传引用
class Solution {
public:
vector<string> binaryTreePaths(TreeNode* root) {
dfs(root, "", ans);
return ans;
}
private:
vector<string> ans;
void dfs(TreeNode *root,string path, vector<string> &ans) {
if(root) {
path = path + to_string(root->val);
if(nullptr == root->left && nullptr == root->right) {
ans.push_back(path);
}
else {
path =path + "->";
dfs(root->left, path, ans);
dfs(root->right, path, ans);
}
}
return;
}
};
class Solution {
public:
vector<string> binaryTreePaths(TreeNode* root) {
stack<string> paths;
if(!root)return paths;
stack<TreeNode *> s;
stack<string> path_stack;
string path;
s.push(root);
path_stack.push(to_string(root->val));
while(!s.empty()) {
TreeNode *node = s.top;s.pop();
path = path_stack.top();
if(node->left == nullptr && node->right == nullptr) {
paths.push(path);
}
if(node->left) {
s.push(node->left);
path_stack(path + "->" + to_string(node->left->val));
}
if(node->right) {
s.push(node->right);
path_stack(path + "->" + to_string(node->right->val));
}
}
}
};
// 使用栈或者队列
// 维护一个队列，存储节点以及根到该节点的路径。一开始这个队列里只有根节点。在每一步迭代中，我们取出队列中的首节点，
// 如果它是一个叶子节点，
// 则将它对应的路径加入到答案中。如果它不是一个叶子节点，则将它的所有孩子节点加入到队列的末尾。当队列为空时，迭代结束。
class Solution {
public:
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> paths;
if(!root) return paths;
queue<TreeNode *> s;
queue<string> path_stack;
string path;
s.push(root);
path_stack.push(to_string(root->val));
while(!s.empty()) {
TreeNode *node = s.front();s.pop();
path = path_stack.front();path_stack.pop();
if(node->left == nullptr && node->right == nullptr) {
paths.push_back(path);
}
if(node->left) {
s.push(node->left);
path_stack.push((path + "->" + to_string(node->left->val)));
}
if(node->right) {
s.push(node->right);
path_stack.push((path + "->" + to_string(node->right->val)));
}
}
return paths;
}
};
|