LeetCode OJ：Binary Tree Paths（二叉树路径）
2024-08-26 22:38:03
Given a binary tree, return all root-to-leaf paths.
For example, given the following binary tree:
1
/ \
2 3
\
5
All root-to-leaf paths are:
["1->2->5", "1->3"]
简单的遍历查找路径问题，代码如下：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<string> binaryTreePaths(TreeNode* root) {
ret.clear();
string s = "";
if(root == NULL) return ret;
dfs(root, s);
for(int i = ; i < ret.size(); ++i){
ret[i].erase(ret[i].begin(), ret[i].begin() + );
}
return ret;
} void dfs(TreeNode * root, string s)
{
stringstream ss;
ss << "->" << root->val;
s += ss.str();
if(root->left == NULL && root->right == NULL){
ret.push_back(s);
return;
}
if(root->left){
dfs(root->left, s);
}
if(root->right){
dfs(root->right, s);
}
}
private:
vector<string> ret;
};
java版本的如下所示，和c++的相比还是要简单很多的，因为处理字符串的函数用起来比较方便的原因，代码如下：
public class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> ret = new ArrayList<String>();
String str = new String();
if(root == null)
return ret;
dfs(root, str, ret);
return ret;
}
public void dfs(TreeNode root, String path, List<String> ret){
if(root.left != null){
path = path + "->" + root.val;
dfs(root.left, path, ret);
path = path.substring(0, path.lastIndexOf("->")); //引用其他的
} //还是要继续使用的，截断即可
if(root.right != null){
path = path + "->" + root.val;
dfs(root.right, path, ret);
path = path.substring(0, path.lastIndexOf("->"));
}
if(root.left == null && root.right == null){
path = path + "->" + root.val;
ret.add(path.substring(2));
path = path.substring(0,path.lastIndexOf("->"));
return;
}
}
}
最新文章
- ggplot2包的说明文档[分享]
- jquery attr()方法 添加，修改，获取对象的属性值。
- Linux程序存储结构与进程结构堆和栈的区别【转】
- BZOJ1507 [NOI2003]Editor
- 你应该知道的JavaScript中NaN的秘密
- 剑指OFFER之二叉树中和为某一值的路径（九度OJ1368）
- 两个不同于LR和jmeter的性能测试工具
- MVC3.0修改jquery.validate.unobtrusive.js实现气泡提示mvc错误
- 【TEGer 在全球架构师峰会】 : 腾讯海外计费系统架构演进
- HTML入门笔记案例展示(1)
- linux下ping命令出现ping: sendto: Network is unreachable
- javascript 模拟日历
- Go语言规格说明书 之 类型（Types）
- python 全栈开发，Day138(scrapy框架的下载中间件,settings配置)
- 怎样使用ZOL一键安装器下载中关村在线的源安装包
- Swagger使用小记
- C#正则表达式MatchCollection类
- FJNUOJ Yehan’s hole（容斥求路径数 + 逆元）题解
- python获取系统时间代码解析
- Java 8 读取文件