/** * 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> res; vector<string> binaryTreePaths(TreeNode* root) { if(root==NULL) return res; string temp =""; back(root,temp); return res; } void back(TreeNode* root, string &temp){ if(root==NULL) // 空节点，不是叶节点 return; string temp1 = to_string(root->val); string val = temp1.append("->"); temp.append(val); if(root->left==NULL&&root->right==NULL){ // 此节点不空，左右子树为空，才为叶节点 temp = temp.substr(0,temp.size()-2); // 去除最后的-> res.push_back(temp); temp = temp.substr(0,temp.size()-to_string(root->val).size()); // 回溯 return; } back(root->left, temp); back(root->right, temp); temp = temp.substr(0,temp.size()-val.size()); // 回溯 } };
可以看到上面的这种解法是因为对temp加了引用，如果不加引用，则可以不用回溯，但是有超时的风险，此题没有超时，不加引用本质上是空间换时间
/** * 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> res; vector<string> binaryTreePaths(TreeNode* root) { if(root==NULL) return res; string temp =""; back(root,temp); return res; } void back(TreeNode* root, string &temp){ if(root==NULL) // 空节点，不是叶节点 return; string temp1 = to_string(root->val); string val = temp1.append("->"); temp.append(val); if(root->left==NULL&&root->right==NULL){ // 此节点不空，左右子树为空，才为叶节点 temp = temp.substr(0,temp.size()-2); // 去除最后的-> res.push_back(temp); // temp = temp.substr(0,temp.size()-to_string(root->val).size()); // 回溯 return; } back(root->left, temp); back(root->right, temp); // temp = temp.substr(0,temp.size()-val.size()); // 回溯 } };