一、二叉树的所有路径
思路：深度优先搜索
- 使用深度优先搜索：即二叉树的前序遍历。
- 1.给一个
string类型的顺序表：vector<string> path，记录每一条可以遍历的路径，如果该节点不为空,给一个临时的存储路径的string，叫node，将该节点的val存入node中 - 2.如果该节点的左子节点和右子节点均为空，说明此节点数一条路径的最后节点，此时将临时的存储路径
node存储到path中。 - 3.如果该节点既不为空，且左右节点不全为空，说明该条路径还未走完，则继续遍历即可。
具体代码如下：
class Solution { public: void PrevOrder(TreeNode* root,string node, vector<string>& path) { //只要该节点不为空，则可继续走 if(root!=nullptr) { node+=to_string(root->val); //只要左右节点都为空，表明获得一条路径 if(root->left == nullptr && root->right == nullptr) { path.push_back(node); } //如果不是以上的情况，则可以继续递归 else { node+="->"; PrevOrder(root->left,node,path); PrevOrder(root->right,node,path); } } } vector<string> binaryTreePaths(TreeNode* root) { string node = ""; vector<string> path; PrevOrder(root,node,path); return path; } };
具体递归展开图如下：
时间复杂度：O(n^2)，因为每次对node进行拷贝构造，所有时间消耗O(n),那么总的时间为O(n^2);最坏空间复杂度O(n)，此时树呈现出链状，最好空间复杂度为O(logN)，此时树为平衡二叉树
二、神奇字符串
思路：模拟双指针
- 首先需要知道题目需要我们做什么。
- 神奇字符串定义：只由’1’，'2’组成，且连续的’1’或者’2’出现的次数组合起来可以生成该字符串。
- 所以我们的目的是构造出神奇字符串。
- 1.构造一个string类，初始化为
s = "122",这样初始化的原因:
- (1)题目给的神奇字符串类就是如此。
- (2)要构造神奇字符串需要从第3位开始构造。
- 2.给定下标
i = 2记录需要构造的字符数字个数，隐式存在的下标j = s.size() - 1，记录需要构造的字符。构造长度为N - 也就是说，构造什么字符取决于j的下标对应的字符，如果
s[j] = '1'，则构造的字符为’2’，如果不是则反过来。构造的个数取决于s[i],如果s[i] = 2,s[j] = 1,则构造的数字为：“22” - 3.构造完成后，遍历s的前n个，统计’1’出现的次数即可。(注意：可能最后一次构造会构造2个字符，导致s的长度为n+1，而不是n，所以不能遍历s，只能遍历s的前n个字符)
- 注：如果 n < 3，则无需再构造，返回1即可。
过程展示：
具体代码如下：
class Solution { public: int magicalString(int n) { string s = "122"; int i = 2; // i表示要构造几位 //要构造什么取决于最后一位,如果s的最后一位是'1'，就构造'2',如果s的最后一位是'2'，就构造'1' for(i = 2;i < n ; ++i) { int len = s[i] - '0'; if(s[s.size()-1] == '2') { while(len--) s+='1'; } else { while(len--) s+='2'; } } //此时遍历n个数字，计算1出现次数，不是遍历s，因为最后一次构造啃s构造了两个数字，导致s的长度是n+1而不是n int count = 0; for(int i = 0;i<n;++i) { if(s[i] == '1') ++count; } return count; } };
时间复杂度O(n)，空间复杂度O(n)，需要构造长度为n的字符串
总结
通过写二叉树，我深知我的递归没有学得扎实，打击心态呀，所以从明天开始着手刷二叉树的题，练练递归。
写这个神奇字符串，还是读不懂题目的，看了答案大佬们的题解才恍然大悟。需要多加强练习。
