力扣Day8

2道easy+9道medium，今天算是把树的部分弄的差不多了，还是习惯递归啊，明天开始图！(OI时期烂的仅次于数论的部分😄)

(medium)173. 二叉搜索树迭代器

byd啥批题干，就是因为我看要求初始化的为最小值才不用迭代的，结果司马正解根本不考虑最小值？我的代码如下：

/**
 * 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) {}
 * };
 */
struct BST{
    int val;
    BST *next;
    BST() : val(1000001), next(nullptr) {}
    BST(int x) : val(x), next(nullptr) {}
};
class BSTIterator {
public:
    void build(int x)
    {
        end->next = new BST(x);
        end = end->next;
        if(now->val >= x)
            now = end;
        return ;
    }
    void BSTsearch(TreeNode* root)
    {
        if(root == NULL)
            return ;
        TreeNode* l = root->left;
        TreeNode* r = root->right;
        BSTsearch(l);
        build(root->val);
        BSTsearch(r);
    }
    BSTIterator(TreeNode* root) {
        now = new BST();
        end = now;
        BSTsearch(root);
    }
    
    int next() {
        int temp = now->val;
        now = now->next;
        return temp;
    }
    
    bool hasNext() {
        return (now != NULL);
    }

private:
    BST* now;
    BST* end;
};

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator* obj = new BSTIterator(root);
 * int param_1 = obj->next();
 * bool param_2 = obj->hasNext();
 */

(medium)222. 完全二叉树的节点个数

第一思路肯定是遍历，但既然要求了效率高于遍历，那就想个别的方法。由于是完全二叉树，所以最后一层之前的所有层都是满的，那么我们设深度为dep，则如果是满二叉树则节点数ans为2^dep-1，我们只需要减去非满的最后一层节点数即可，即到达深度为dep-1的层，若其left为空则ans-1，若其right为空则ans-1。效率为O(dep+2^(dep-1)。代码如下：

/**
 * 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 findleft(TreeNode* root,int dep)
    {
        if(root == NULL)
            return dep;
        TreeNode* l = root->left;
        return findleft(l,dep + 1);
    }
    void geth(TreeNode* root,int dep)
    {
        if(root == NULL)
            return ;
        TreeNode* l = root->left;
        TreeNode* r = root->right;
        if(dep == maxdep - 1)
            ans = ans - (l == NULL) - (r == NULL);
        else
        {
            geth(l, dep + 1);
            geth(r, dep + 1);
        }
    }
    int countNodes(TreeNode* root) {
        maxdep = findleft(root, 0);
        ans = (1 << maxdep) - 1;
        geth(root, 1);
        return ans;
    }
private:
    int maxdep;
    int ans;
};

(medium)236. 二叉树的最近公共祖先

经典LCA。由于是指针的所以不能用数组定义，只能哈希表指向，效率要低很多，但没法。我的思路就是记录每个点的上一个点fa[i](fa[root] = root)，然后记录每个点的depth，如果p!=q则让深度更深的那个指针i=fa[i]，直到p==q。代码如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void bl(TreeNode* root,int dep)
    {
        if(root == NULL)
            return ;
        TreeNode* l = root->left;
        TreeNode* r = root->right;
        depth[root] = dep;
        if(l != NULL)
            fa[l] = root;
        if(r != NULL)
            fa[r] = root;
        bl(l, dep + 1);
        bl(r, dep + 1);
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        fa[root] = root;
        bl(root, 0);
        while(p != q)
        {
            if(depth[p] > depth[q])
                p = fa[p];
            else
                q = fa[q];
        }
        return p;
    }
private:
    unordered_map<TreeNode*,TreeNode*> fa;
    unordered_map<TreeNode*,int> depth;
};

(medium)199. 二叉树的右视图

本质也是一个遍历顺序的问题，只要你右边是最后遍历的即可。用a[i]表示在当前扫满情况下深度为i的地方所能看到节点的值。代码如下：

/**
 * 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:
    void bl(TreeNode* root,int dep)
    {

        if(root == NULL)
            return ;
        maxdep = max(maxdep , dep);
        if(a.size()<=dep)
            a.push_back(0);
        TreeNode* l = root->left;
        TreeNode* r = root->right;
        bl(l , dep + 1);
        a[dep] = root->val;
        bl(r , dep + 1);
        return ;
    }
    vector<int> rightSideView(TreeNode* root) {
        maxdep = -1;
        bl(root , 0);
        return a;
    }
private:
    vector<int> a;
    int maxdep;
};

(easy)637. 二叉树的层平均值

同上，只不过是把a[dep]记录的值变为深度为dep的当前和，加个num[dep]表示当前深度为num的节点数。代码如下：

/**
 * 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:
    void bl(TreeNode* root,int dep)
    {

        if(root == NULL)
            return ;
        maxdep = max(maxdep , dep);
        if(sum.size() <= dep)
        {
            sum.push_back(0);
            num.push_back(0);
        }
        TreeNode* l = root->left;
        TreeNode* r = root->right;
        bl(l , dep + 1);
        sum[dep] += root->val;
        num[dep]++;
        bl(r , dep + 1);
        return ;
    }
    vector<double> averageOfLevels(TreeNode* root) {
        maxdep = -1;
        bl(root , 0);
        vector<double> ans;
        for(int i = 0 ; i <= maxdep ; i++)
            ans.push_back(((double)sum[i]/(double)num[i]));
        return ans;
    }
private:
    vector<long long> sum;
    vector<int> num;
    int maxdep;
};

(medium)102. 二叉树的层序遍历

byd好像只能用vector了，学会了 if(ans.size() <= dep) ans.push_back(vector<int>());。那就也同上，代码如下：

/**
 * 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:
    void bl(TreeNode* root,int dep)
    {

        if(root == NULL)
            return ;
        if(ans.size() <= dep)
            ans.push_back(vector<int>());
        TreeNode* l = root->left;
        TreeNode* r = root->right;
        bl(l , dep + 1);
        ans[dep].push_back(root->val);
        bl(r , dep + 1);
        return ;
    }
    vector<vector<int>> levelOrder(TreeNode* root) {
        bl(root , 0);
        return ans;
    }
private:
    vector<vector<int>> ans;
};

(medium)103. 二叉树的锯齿形层序遍历

也是同上的遍历，只不过在输出之前需要判断一下深度。由于我的起始深度为0，则为偶数的时候不反转，为奇数的时候反转即可。代码如下：

/**
 * 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:
    void bl(TreeNode* root,int dep)
    {

        if(root == NULL)
            return ;
        if(ans.size() <= dep)
            ans.push_back(vector<int>());
        TreeNode* l = root->left;
        TreeNode* r = root->right;
        bl(l , dep + 1);
        ans[dep].push_back(root->val);
        bl(r , dep + 1);
        return ;
    }
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        bl(root , 0);
        for(int i = 0 ; i < ans.size() ; i++)
        {
            if(i & 1)
                reverse(ans[i].begin(), ans[i].end());
        }
        return ans;
    }
private:
    vector<vector<int>> ans;
};

(easy)530. 二叉搜索树的最小绝对差

也挺简单，由于是二叉搜索树，因而其中序遍历值肯定是递增的，所以我们中序遍历把每个点的值存进数组，然后a[i+1]-a[i]的非0最小值即为结果。代码如下：

/**
 * 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:
    void bl(TreeNode* root)
    {

        if(root == NULL)
            return ;
        TreeNode* l = root->left;
        TreeNode* r = root->right;
        bl(l);
        a.push_back(root->val);
        cnt++;
        bl(r);
        return ;
    }
    int getMinimumDifference(TreeNode* root) {
        ans = INT_MAX;
        cnt = 0;
        bl(root);
        for(int i = 0 ; i < cnt - 1 ; i++)
        {
            int temp = a[i + 1] - a[i];
            if(temp != 0)
                ans = min(ans , temp);
        }
        return ans;
    }
private:
    vector<int> a;
    int ans;
    int cnt;
};

(medium)230. 二叉搜索树中第K小的元素

由于是上题之后做的，所以我想当然就把上到题的思路拿过来，输出a[k-1]不就完了。代码如下：

/**
 * 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:
    void bl(TreeNode* root)
    {

        if(root == NULL)
            return ;
        TreeNode* l = root->left;
        TreeNode* r = root->right;
        bl(l);
        a.push_back(root->val);
        cnt++;
        bl(r);
        
        return ;
    }
    int kthSmallest(TreeNode* root, int k) {
        bl(root);
        return a[k - 1];
    }
private:
    vector<int> a;
    int cnt;
};

(medium)98. 验证二叉搜索树

初始想法是遍历过程中存储以root为根的树中最大值和最小值，然后比较root->val和maxn[l]与minl[r]；写倒是写出来了，但效率一般，于是就想到那我们就中序遍历一遍，检查是否有序就完事了。代码如下：

/**
 * 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:
    void bl(TreeNode* root)
    {
        if(root == NULL)
            return ;
        TreeNode* l = root->left;
        TreeNode* r = root->right;
        bl(l);
        ans.push_back(root->val);
        bl(r);
        return ;
    }
    bool isValidBST(TreeNode* root) {
        bl(root);
        for(int i = 0 ; i < ans.size() - 1 ; i++)
        {
            if(ans[i] >= ans[i + 1])
                return 0;
        }
        return 1;
    }
private:
    vector<int> ans;
};

(medium)380. O(1) 时间插入、删除和获取随机元素

这道题之前觉得用rand肯定会很恶心所以没做，放到现在才做。其实就是一个哈希表+数组的东西，哈希表a[val]表示val在数组中的位置。删除val则是把数组最后一位放到a[val]，然后pop_back。代码如下：

class RandomizedSet {
public:
    RandomizedSet() {
        temp.clear();
        a.clear();
    }
    
    bool insert(int val) {
        if(a[val])
            return 0;
        temp.push_back(val);
        a[val] = temp.size();
        return 1;
    }
    
    bool remove(int val) {
        if(!a[val])
            return 0;
        int pos = a[val] - 1;
        int lastval = temp.back();
        temp[pos] = lastval;
        a[lastval] = pos + 1;
        temp.pop_back();
        a[val] = 0;
        return 1;
    }
    
    int getRandom() {
        int i = rand() % temp.size();
        return temp[i];
    }
private:
    //a表示val的位置,a[val]-1表示其在temp中的位置
    unordered_map<int,int> a;
    vector<int>temp;
};

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet* obj = new RandomizedSet();
 * bool param_1 = obj->insert(val);
 * bool param_2 = obj->remove(val);
 * int param_3 = obj->getRandom();
 */