二叉树的所有路径
递归法（非回溯，浪费内存）
直接递归字符串，每一次递归都产生一个新字符串。没有回溯的过程，浪费空间。
/** * 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: vector<string> result; void get_road(TreeNode* cur , string &s) { if(cur == nullptr) return; s += to_string(cur->val); if(cur->left == nullptr && cur->right == nullptr ) { result.push_back(s); return; }else if(cur->left != nullptr && cur->right == nullptr ) { s += "->"; string s1 =s; get_road(cur->left ,s1); }else if (cur->left == nullptr && cur->right != nullptr ) { s += "->"; string s1 =s; get_road(cur->right ,s1); }else { s += "->"; string s1 =s; string s2 =s; get_road(cur->left ,s1); get_road(cur->right ,s2); } return; } vector<string> binaryTreePaths(TreeNode* root) { string s; get_road(root ,s); return result; } };
递归回溯法
使用一个数组来保存路径数据，然后在转换成字符串。
效率略低，充分体现回溯的思想。
/** * 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: void get_road(TreeNode* cur , vector<string> &result , vector<int> &path) { if(cur == nullptr) return; path.push_back(cur->val); if(cur->left == nullptr && cur->right == nullptr ) { string tmp; for(int i=0 ; i < path.size()-1 ;i++ ) { tmp += to_string(path[i]); tmp += "->"; } tmp += to_string(path[path.size()-1]); result.push_back(tmp); return; } if(cur->left != nullptr ) { get_road(cur->left,result,path); path.pop_back(); } if(cur->right != nullptr) { get_road(cur->right,result,path); path.pop_back(); } return; } vector<string> binaryTreePaths(TreeNode* root) { vector<string> result; vector<int> path; if(root == nullptr) return result; get_road(root ,result , path); return result; } };
递归回溯（精简版）
不使用数组进行纪录，直接进行字符串回溯
/** * 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: void get_road(TreeNode* cur , vector<string> &result , string path) { if(cur == nullptr) return; path += to_string(cur->val); if(cur->left == nullptr && cur->right == nullptr ) { result.push_back(path); return; } if(cur->left != nullptr ) { get_road(cur->left,result, path + "->"); } if(cur->right != nullptr) { get_road(cur->right,result, path + "->"); path.pop_back(); } return; } vector<string> binaryTreePaths(TreeNode* root) { vector<string> result; string path; if(root == nullptr) return result; get_road(root ,result , path); return result; } };
二刷
/** * 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: vector<string> result; void back_trak(TreeNode* cur , string tmp) { if(cur == nullptr) return; if(cur->left == nullptr && cur->right == nullptr) { tmp += to_string(cur->val); result.push_back(tmp); return; }; tmp += to_string(cur->val); tmp += "->"; back_trak(cur->left,tmp); back_trak(cur->right,tmp); return; } vector<string> binaryTreePaths(TreeNode* root) { if(root == nullptr) return result; string tmp; back_trak(root,tmp); return result; } };
