LeetCode257.二叉树的所有路径
·

题目:
- 给你一个二叉树的根节点
root,按 任意顺序 ,返回所有从根节点到叶子节点的路径。叶子节点 是指没有子节点的节点。
示例:

- 输入: r o o t = [ 1 , 2 , 3 , n u l l , 5 ] root = [1,2,3,null,5] root=[1,2,3,null,5]
- 输出: [ " 1 − > 2 − > 5 " , " 1 − > 3 " ] ["1->2->5","1->3"] ["1−>2−>5","1−>3"]
解题思路一:(递归)
-
确定递归函数的参数和返回值:
传入当前节点、结果集、路径集,采用引用方式传递,无需返回值。
void dfs(TreeNode* cur, vector<string>& res, vector<int>& path) -
确定终止条件:
每遍历一个节点就先将其加入到路径集中,然后判断该节点左右孩子是否都为空,若都为空代表到达了叶子节点,进行相应处理与返回。
path.push_back(cur->val); if(cur->left == NULL && cur->right == NULL){ string subPath = ""; for(int i = 0; i < path.size(); i++){ subPath += to_string(path[i]); if(i == path.size() - 1) break; subPath += "->"; } res.push_back(subPath); return; } -
确定单层递归逻辑:
递归左右子树,需要对
path进行回溯。if(cur->left){ dfs(cur->left, res, path); path.pop_back(); } if(cur->right){ dfs(cur->right, res, path); path.pop_back(); }
C++版整体代码
class Solution {
public:
void dfs(TreeNode* cur, vector<string>& res, vector<int>& path){
// 每递归遍历一个节点,就将其加入到路径集中待后续处理使用
path.push_back(cur->val);
// 当递归遍历到叶子节点,进行处理
if(!cur->left && !cur->right){
string tempStr = "";
for(int i = 0; i < path.size(); i++){
tempStr += to_string(path[i]);
if(i == path.size() - 1) break;
tempStr += "->";
}
res.push_back(tempStr);
return;
}
if(cur->left){
dfs(cur->left, res, path);
path.pop_back();
}
if(cur->right){
dfs(cur->right, res, path);
path.pop_back();
}
}
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> res;
vector<int> path;
if(!root) return res;
dfs(root, res, path);
return res;
}
};
Java实现版本
class Solution {
public void dfs(TreeNode cur, List<String> res, List<Integer> path){
path.add(cur.val);
if(cur.left == null && cur.right == null){
String tempStr = "";
for(int i = 0; i < path.size(); i++){
tempStr += String.valueOf(path.get(i));
if(i == path.size() - 1) break;
tempStr += "->";
}
res.add(tempStr);
return;
}
if(cur.left != null){
dfs(cur.left, res, path);
path.remove(path.size() - 1);
}
if(cur.right != null){
dfs(cur.right, res, path);
path.remove(path.size() - 1);
}
}
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
if(root == null) return res;
dfs(root, res, path);
return res;
}
}
更多推荐

所有评论(0)