力扣Hot100题单个人计划c++版（三）

力扣Hot100题单个人计划c++版（一）
力扣Hot100题单个人计划c++版（二）
力扣Hot100题单个人计划c++版（三）

刷题链接：力扣Hot 100
每日一题，每日一更，白板手写。

• 41.二叉树的层序遍历
• 42.二叉树的最大深度

10.11打卡
层序遍历很基础的算法了，按照每层返回一个vector的话，一开始想到用两个队列循环取每一层和下一层，然后在转成vector，当然题解更巧妙的做法是记住每层的大小即可。

class Solution {
public:
    vector> levelOrder(TreeNode* root) {
        if(root==nullptr)return {};
        vector> ans;
        queue q;
        q.push(root);
        int cnt=-1;
        while(!q.empty()){
            int clen=q.size();
            ++cnt;
            ans.push_back(vector());
            while(clen--){
                auto pos=q.front();q.pop();
                ans[cnt].push_back(pos->val);
                if(pos->left)q.push(pos->left);
                if(pos->right)q.push(pos->right);
            }
        }
        return ans;
    }
};

10.12打卡
递归可以有两种写法，一种是像下面这段代码一样，根节点初始化为0，从上往下搜索，每搜索一层就加一。

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

也可以直到搜索至叶节点，让叶节点的下一层空节点为0，这样叶节点就是最低层为1，往上返回的过程中不断加1。

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

还有可以用BFS，不断想下扩展层数，到边界就返回层数。广搜写太多了，此处就不写了。