lc-day2

发表于

257. ⼆叉树的所有路径

这个题出的好呀，一个简单题让我吃尽苦头

257

先说遍历，感觉用不了广搜，只能深搜，而且深搜还得用先序遍历

先序遍历的原因：先序遍历的顺序是“中左右”，这题我把“中”当做递归出口，而“左右”当做递归入口，只有在经历了大量搜索之后，然后判断已经到叶结点了，我就保存结果，执行return，递归结束

这个题难住我的一个地方之一就是回溯，根据Carl的理论，有递归式就必须有回溯式，递归和回溯永远是在一起的。对于回溯我的理解就是恢复现场

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    vector<string> result;
    vector<int> path;
    vector<string> binaryTreePaths(TreeNode* root) {
        dfs(root);
        return result;
    }
    void dfs(TreeNode* root){
        path.push_back(root->val);
        if(root->left == nullptr && root->right == nullptr) {
            string s;
            s += to_string(path[0]);
            for(int i = 1; i < path.size(); i++){
                s += "->";
                s += to_string(path[i]);
            }
            result.push_back(s);
            return ;
        }
        if(root->left) {
            dfs(root->left);
            path.pop_back();
        }
        if(root->right){
            dfs(root->right);
            path.pop_back();
        }
    }
};

剩下的没啥说的了，都是常规操作

100. 相同的树

待更新

101. 对称⼆叉树

待更新