day68—DFS—二叉树的所有路径（LeetCode-257）

题目描述

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

示例 1：

输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]

示例 2：

输入：root = [1]
输出：["1"]

提示：

• 树中节点的数目在范围 [1, 100] 内
• -100 <= Node.val <= 100

解决方案：

1、越界判断：结点为空

2、结束条件：左右子节点为空

3、路径不可用“引用”：下一条路径会刷新路径

函数源码：

完整版： 

/*** 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:string a="->";vector<string> binaryTreePaths(TreeNode* root) {vector<string> vx={};if(root==NULL)  return vx;string path;path=to_string(root->val);if(root->left==NULL&&root->right==NULL)   {vx.push_back(path);return vx;}path+=a;dfs(root->left,vx,path);dfs(root->right,vx,path);return vx;}void  dfs(TreeNode* node,vector<string>&ans,string path){if(node==NULL)  return;path+=to_string(node->val);if(node->left==NULL && node->right==NULL) {ans.push_back(path);cout<<endl<<path<<endl;return;}path+=a;dfs(node->left,ans,path);dfs(node->right,ans,path);}};

改良版：（减少代码量）

/*** 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:string a="->";vector<string> binaryTreePaths(TreeNode* root) {vector<string> vx={};string path;dfs(root,vx,path);return vx;}void  dfs(TreeNode* node,vector<string>&ans,string path){if(node==NULL)  return;path+=to_string(node->val);if(node->left==NULL && node->right==NULL) {ans.push_back(path);cout<<endl<<path<<endl;return;}path+=a;dfs(node->left,ans,path);dfs(node->right,ans,path);}};