算法康复训练17

1. 知识点总结

划水滑的好快乐哈😜

题目	难度	知识点
二叉树的最大深度	🐸	层次遍历
从前序与中序遍历序列构造二叉树	🐸	基础题,但是忘记板子的话会很难受

2. 分题题解

2.1 二叉树的最大深度

emm这个时间复杂度和空间复杂度好像在被吊打哇：

执行用时：12 ms, 在所有 C++ 提交中击败了24.80%的用户

内存消耗：18.5 MB, 在所有 C++ 提交中击败了9.14%的用户

/**
 * 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:
    int ans=0;
    void levelTravel(TreeNode* root){
        queue<TreeNode*>q;
        root->val=1;
        q.push(root);
        while(!q.empty()){
            TreeNode *top=q.front();
            q.pop();
            //用值来代替
            int level=top->val;
            ans=level;
            //下一个
            if(top->left!=NULL){
                top->left->val=level+1;
                q.push(top->left);
            }
            //下一个
            if(top->right!=NULL){
                top->right->val=level+1;
                q.push(top->right);
            }
        }
    }
    int maxDepth(TreeNode* root) {
        //求二叉树的深度
        if(root==NULL){
            return 0;
        }
        levelTravel(root);
        return ans;
    }
};

官方题解给的是深度优先搜索……emm好久没用那个来着（借口😅

2.2 从前序与中序遍历序列构造二叉树

确实忘记了,Wa了三次才修正对😣

PTA板子题,参考晴神算法笔记

class Solution {
public:
    vector<int>pre,in;
    int len;
    TreeNode*build(int preL,int preR,int inL,int inR){
        cout<<preL<<" "<<preR<<" "<<inL<<" "<<inR<<endl;
        if(preR>=len||inR>=len||preL>=len||inL>=len||inR<inL||preR<preL){
            return NULL;
        }
        TreeNode*root=new TreeNode(pre[preL]);
        if(preL==preR){
            return root;
        }
        //下面找对应位置的中序下标
        int k=inL;
        for(;k<=inR;k++){
            if(in[k]==pre[preL]){
                break;
            }
        }
        int dis=k-inL;
        root->left=build(preL+1,preL+dis,inL,k-1);
        root->right=build(preL+dis+1,preR,k+1,inR);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.size()==0){
            return NULL;
        }else{
            pre=preorder;in=inorder;
            len=pre.size();
            TreeNode*root=build(0,len-1,0,len-1);
            return root;
        }

    }
};

3. 参考资料