代码随想录算法训练营29期Day21|LeetCode 530,501,236

???文档讲解：二叉搜索树的最小绝对差??二叉搜索树中的众数??二叉树的最近公共祖先

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

题目链接：https://leetcode.cn/problems/minimum-absolute-difference-in-bst/description/

思路：

? ? ? ? 本题目要求我们返回?树中任意两不同节点值之间的最小差值?。

? ? ? ? 很朴素的一个思路是，我们枚举每个点，再枚举一个点和其进行求差值，取最小值即可。这个做法很好想到，可惜过不了，因为时间复杂度为O()。

? ? ? ? 又因为我们知道这是一颗二叉搜索树，那么和每个点的差值最小的一定在哪呢？如果在其左子树中，则一定是左子树的最大值，如果在其右子树中，一定是右子树中的最小值。因为它们的大小与子树根节点的值最接近。为什么不考虑子树之外的点呢？因为这是一颗二叉搜索树，子树外的节点的值一定比子树内节点的值距子树根节点更远，不然这不符合二叉搜索树的性质。

? ? ? ? 根据我们上面的判断，针对每个节点，我们只需要获得左右子树的最大值和最小值共四个节点值。利用左子树的最大值与根节点作差、右子树的最小值和根节点作差，均与记录的最小值比较，更小的话就更新答案。同时利用这四个值更新整个子树的最大值和最小值，向上层回溯即可。

? ? ? ? 整颗子树遍历回溯结束后，记录的差值的最小值就是树中任意两不同节点值之间的最小差值。

核心代码：

/**
 * 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 {
private:
    int ans=100005;
    vector<int> calc(TreeNode* cur){
        vector<int> nums;
        int minnum=cur->val,maxnum=cur->val;
        if(cur->left){
            vector<int> numl=calc(cur->left);
            if(minnum>numl[0]) minnum=numl[0];
            if(ans>abs(cur->val-numl[1])) ans=abs(cur->val-numl[1]);
        }
        if(cur->right){
            vector<int> numr=calc(cur->right);
            if(maxnum<numr[1]) maxnum=numr[1];
            if(ans>abs(numr[0]-cur->val)) ans=abs(numr[0]-cur->val);
        }
        nums.push_back(minnum);
        nums.push_back(maxnum);
        return nums;
    }
public:
    int getMinimumDifference(TreeNode* root) {
        calc(root);
        return ans;
    }
};

501.二叉搜索树中的众数

题目链接：https://leetcode.cn/problems/find-mode-in-binary-search-tree/description/

思路：

? ? ? ? 这题其实挺简单的，思路也很简单。

? ? ? ? 首先遍历二叉树，什么遍历方式都可以，把二叉树中的值都取出来，丢到map中记录一下每个值出现了多少次。再遍历map把出现最多的数字加到答案中即可。

? ? ? ? 这个做法无视是不是二叉搜索树。

核心代码：

/**
 * 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:
    vector<int> findMode(TreeNode* root) {
        map<int,int> mp;
        queue<TreeNode*> q;
        vector<int> ans;
        int maxnum=-1;
        if(root) q.push(root);
        while(!q.empty()){
            TreeNode* cur;
            int n=q.size();
            while(n--){
                cur=q.front();
                q.pop();
                mp[cur->val]++;
                if(cur->left) q.push(cur->left);
                if(cur->right) q.push(cur->right);
            }
        }
        for(auto i=mp.begin();i!=mp.end();i++)
          if(i->second>maxnum) maxnum=i->second;
        for(auto i=mp.begin();i!=mp.end();i++)
          if(i->second==maxnum) ans.push_back(i->first);
        return ans;
    }
};

700.二叉树的最近公共祖先

题目链接：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/

思路：

? ? ? ?这题算是树上最近公共祖先（LCA）的模板题，而且还算是弱化版，因为只有两个叉，并且也不需要类似ST表的优化。写法上也省事一些，比ACM模式下好写很多。但这题第一次做肯定是不好理解的。

? ? ? ? 我们知道这样一件事，找公共祖先，肯定是从底向上找更好，因为从上到下要分叉，也不知道什么时候结束，从下向上呢则会合并叉，合并到碰头的时候自然就找到了。

? ? ? ? 那我们怎么从底向上查找呢，肯定是递归加回溯了。利用回溯上来的值进行判断就行了。

所以我们就要思考回溯什么值。

? ? ? ? 首先我们知道，找的是p和q的最近公共祖先。那我们向下搜索到p或者q的时候，其实就不用再向下找了，开始向上回溯就可以了。到达空节点也不用向下了，因为向下没有了。所以我们就分析出回溯值了：如果碰到p点或者q点或者空节点，返回这个点本身即可。

? ? ? ? 其次，我们开始分析如何根据回溯值进行判断。由于我们这个写法本身就属于自底向上了。因此我们每次对左右子树的回溯值进行判断，如果左右子树回溯值均不为空，证明当前这个点就是最近公共祖先，返回这个点即可。如果两个回溯值一个空另一个非空，则把这个回溯值接着向上回溯即可。如果两个回溯值均为空，证明没找到，也回溯空即可。

? ? ? ? 最后回溯到上面的一定就是最近公共祖先，如果为空，证明没有。

? ? ? ? 注意我们这个做法针对p和q其中一个是另一个的祖先时也是正确的，因为这时的答案就是p或q，我们遇到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:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == q || root == p || root == NULL)
            return root;
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if (left != NULL && right != NULL)
            return root;
        if (left == NULL)
            return right;
        return left;
    }
};

今日总结

????????今日学习时长3h，题目不算难，但我的解法依旧不算好，没来的及写好的，后面再回来认真总结这几天的题目。