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

发布时间:2024年01月16日

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

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

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

思路:

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

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

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

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

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

核心代码:

/**
 * 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,题目不算难,但我的解法依旧不算好,没来的及写好的,后面再回来认真总结这几天的题目。

文章来源:https://blog.csdn.net/tlingyuqi/article/details/135636356
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。