【小白爬Leetcode257】二叉树的所有路径 Binary Tree Paths
题目方法一 深度优先搜索方法二 广度优先搜索关于C++中int转成string
题目
Leetcode332
e
a
s
y
\color{#5aB726}{easy}
easy 点击进入原题链接：重新安排行程 Reconstruct Itinerary
Given a binary tree, return all root-to-leaf paths. Note: A leaf is a node with no children.
方法一 深度优先搜索
class Solution {
public:
vector
<string
> binaryTreePaths(TreeNode
* root
) {
if(!root
) return routes
;
DFS(root
,route
);
return routes
;
}
private:
vector
<string
> routes
;
string route
;
void DFS(TreeNode
* root
,string route
){
route
+= to_string(root
->val
);
if(!root
->left
&& !root
->right
){
routes
.push_back(route
);
return;
}
route
+= "->";
if(root
->left
){
DFS(root
->left
,route
);
}
if(root
->right
){
DFS(root
->right
,route
);
}
}
};
重点在复杂度分析上： 放上官方解答： 这里空间复杂度的分析，是基于每层递归都要储存一个path路径字符串，根据等比数列求和公式，算出的关于二叉树高度的平方复杂度。
方法二 广度优先搜索
class Solution {
public:
vector
<string
> binaryTreePaths(TreeNode
* root
) {
vector
<string
> routes
;
if(!root
) return routes
;
string route
;
route
+= to_string(root
->val
);
queue
<string
> route_queue
;
route_queue
.push(route
);
queue
<TreeNode
*> node_quque
;
node_quque
.push(root
);
while(!node_quque
.empty()){
string cur_route
= route_queue
.front();
route_queue
.pop();
TreeNode
* cur_node
= node_quque
.front();
node_quque
.pop();
if(!cur_node
->left
&&!cur_node
->right
){
routes
.push_back(cur_route
);
continue;
}
if(cur_node
->left
) {
route_queue
.push(cur_route
+ "->"+to_string(cur_node
->left
->val
));
node_quque
.push(cur_node
->left
);
}
if(cur_node
->right
){
route_queue
.push(cur_route
+ "->"+to_string(cur_node
->right
->val
));
node_quque
.push(cur_node
->right
);
}
}
return routes
;
}
};
重点在复杂度分析上： 放上官方解答：
关于C++中int转成string
一开始我是这样写的：
route
+= char(root
->val
);
想把int型强制转换成char型加到路径里，但是too naive，这样是把root->val认为是ASCII码值
后来改成
route
+= root
->val
+'0';
但是这样只对个位数有效，毕竟ASCII码里只有0~9的编码。
最后改成才解决的问题
route
+= to_string(root
->val
);
