自己一直还是比较努力的，不知道“摆烂”是种什么状态，但最近的自己迷茫，深深感觉到现在的自己不就处于“摆烂”的状态吗？没有目标没有计划，只失败了一次就无信心可言了，难的事也懒得做，就这么空耗着。人生短暂，多去尝试多去挑战，慢慢重拾专注的状态。利用 blog 记录下每天学习和刷LeetCode的题解。知道没人会看LeetCode的题解，之前的心态是不想发LeetCode练习在blog上的。但现在的自己需要这份坚持，很多题因为没有思绪又看着别人很长的代码就开始知难而退。曾经多么害怕失败，总以为一次失败就会击垮自己。可是当真正失败时，却发现日子还是要一天天过的。

cs50-introduction

What ultimately matters in this course is not so much where you end up relative to your classmates but where you end up relative to yourself when you began.

正好今天整理笔记的时候看到这张截图，大概是2021年3月看 YouTube 时截取的，是外国一门CS课程 introduction 的最后教授对学生说的。印象中好像是 CS50 ，但也不确定了，当时在 YouTube 零散看了好几门优秀的外国课程（其实知乎、bilibili 一搜就有）。当时看的感受就是为什么没有早点利用互联网的优质课程和资源，但也知道后悔无用，唯一能抓住的就是现在。所以同样是这个时候，“往者不可谏，来者犹可追”。好多要学的要做的，打起精神来 💪。

LeetCode 每天刷题，使用 C++ 和 Java 一起刷题，第一遍做不出来的使用 C++ 参考别人题解完成，第二天再使用 Java 写出自己的题解（虽然Java用的多，但刷算法题一般都是C++比较熟练），直到完全掌握。

Recursion 递归

二叉树

二叉树使用递归的地方很多。

平衡二叉树AVL

110. Balanced Binary Tree

自顶向下的递归

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    int getHeight(TreeNode* root){
        if(root==nullptr) return 0;
        return max(getHeight(root->left),getHeight(root->right))+1;
    }
    bool isBalanced(TreeNode* root) {
        if(root==nullptr) return true;
        return abs(getHeight(root->left)-getHeight(root->right))<=1 && isBalanced(root->left) && isBalanced(root->right);
    }
};
//注意 abs 不能忽略。

注意：下述中的n都是二叉树的节点个数。自己总是理所当然、凭感觉是这样的时间复杂度和那样的空间复杂度，但真正未曾深入思考过。

时间复杂度：

最坏情况下，二叉树为满二叉树，需要遍历二叉树中的所有节点，时间复杂度是O(n)

平均时间复杂度：O(nlogn) 二叉树高度O(h)=O(log n)

最坏时间复杂度：O(n^2) 链式二叉树，二叉树高度为O(h)=O(n)

空间复杂度：O(n) 递归调用的层数不会超过n

可以看到自顶向下的getHeight被重复调用，时间复杂度很高。所以优化采用自底向上的递归，整个过程类似后序遍历。

自底向上的递归

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        return getHeight(root)>=0;
    }
    int getHeight(TreeNode* root){
        if(root==nullptr) return 0;
        int leftHeight=getHeight(root->left);
        int rightHeiht=getHeight(root->right);
        if(leftHeight==-1 || rightHeiht==-1 || abs(leftHeight-rightHeiht)>1){
            return -1;
        }
        return max(leftHeight,rightHeiht)+1;
    }
};

递归边界：比如自己总是会忽略if(root==nullptr) return 0;

考虑周全：递归就像套娃🪆，二叉树就是左子树+右子树+自身节点

时间复杂度：O(n) 最坏情况下遍历所有的二叉树结点。

空间复杂度：O(n)

104. Maximum Depth of Binary Tree

深度优先搜索DFS——后序遍历

1
2
3
4
5
6
7

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root==nullptr) return 0;
        return max(maxDepth(root->left),maxDepth(root->right))+1;
    }
};

时间复杂度：O(n)

空间复杂度：O(height)

广度优先搜索BFS——层序遍历

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root==nullptr) return 0;
        queue<TreeNode*> q;
        q.push(root);
        int depth=0;
        while(!q.empty()){
            depth++;
            int size=q.size();
            while(size--){
                TreeNode* node=q.front();
                q.pop();
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
            }
        }
        return depth;
    }
};

时间复杂度：O(n)

空间复杂度：O(n)

队列里存放的是当前层的所有节点，每次拓展下一层的时候,将队列里的所有节点都拿出来拓展，即一层一层地进行拓展。

这种思路的同类型题：

102. Binary Tree Level Order Traversal

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    vector<int> levelOrder(TreeNode* root) {
        vector<int> v;
        queue<TreeNode*> q;
        if(root) q.push(root); //这边要判空
        while(!q.empty()){
            int size=q.size();
            while(size--){
                TreeNode* node=q.front();
                q.pop();
                v.push_back(node->val);
                if(node->left) q.push(node->left); 
                if(node->right) q.push(node->right);
            }
        }
        return v;
    }
};

1
2
3
4

还在习惯性地只写q.push(root),导致下面的报错：
Line 21: Char 35: runtime error: member access within null pointer of type 'TreeNode' (solution.cpp)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior prog_joined.cpp:31:35
发现自己对于LeetCode刷题runtime error: null pointer这种错误总是不认真，总是会疏忽。值得注意反思。

107. Binary Tree Level Order Traversal II

637. Average of Levels in Binary Tree