算法刷题Day 21 二叉搜索树的最小绝对差+二叉搜索树中的众数+二叉树的最近公共祖先

这篇具有很好参考价值的文章主要介绍了算法刷题Day 21 二叉搜索树的最小绝对差+二叉搜索树中的众数+二叉树的最近公共祖先。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

Day 21 二叉树

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

递归

递归中保存前一个节点的指针的方法,需要再学习,巩固一下

class Solution {
    int minDiff = INT_MAX;
    TreeNode *pre = nullptr;

    void traverse(TreeNode *root)
    {
        if (!root) return;
        traverse(root->left);
        if (pre)
        {
            int curDiff = abs(root->val - pre->val);
            if (curDiff < minDiff)
            {
                minDiff = curDiff;
            }
        }
        pre = root;
        traverse(root->right);
    }

public:
    int getMinimumDifference(TreeNode* root) {
        traverse(root);
        return minDiff;
    }
};

迭代

class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        stack<TreeNode*> stk;
        TreeNode *pNode = root;
        int pre = INT_MAX, minDiff = INT_MAX;

        while (pNode || !stk.empty())
        {
            if (pNode)
            {
                stk.push(pNode);
                pNode = pNode->left;
            }
            else
            {
                pNode = stk.top();
                stk.pop();
                int curDiff = abs(pNode->val - pre);
                if (curDiff < minDiff)
                {
                    minDiff = curDiff;
                }
                pre = pNode->val;
                pNode = pNode->right;
            }
        }

        return minDiff;
    }
};

501. 二叉搜索树中的众数

一下子就想到的方法:遍历一遍二叉搜索树,把各个节点的值存进哈希表里(节点值——键,出现频率——值),再遍历哈希表找众数

一般方法

class Solution {
public:
    vector<int> findMode(TreeNode* root) {
        unordered_map<int, int> table;
        stack<TreeNode*> stk;
        TreeNode *cur = root;

        while (cur || !stk.empty())
        {
            if (cur)
            {
                stk.push(cur);
                cur = cur->left;
            }
            else
            {
                cur = stk.top();
                stk.pop();
                table[cur->val]++;
                cur = cur->right;
            }
        }

        vector<int> rst;
        int time = 0;

        for (auto &[key, val] : table)
        {
            if (val > time)
            {
                time = val;
                rst.clear();
                rst.push_back(key);
            }
            else if (val == time)
            {
                rst.push_back(key);
            }
        }

        return rst;
    }
};

既然是二叉搜索树,中序遍历就是有序的。有序的话,我们就有希望在线性时间内完成找众数的操作(因为相同的数字都扎堆连在一起)

递归

class Solution {
    vector<int> rst;
    TreeNode *pre = nullptr;
    int maxTime = 0, curTime = 0;

    void traverse(TreeNode *root) 
    {
        if (!root) return;
        traverse(root->left);
        if (pre)
        {
            if (pre->val == root->val)
            {
                curTime++;
            }
            else
            {
                curTime = 1;
            }
        }
        else // 是访问的第一个节点
        {
            curTime = 1;
        }

        pre = root;
        if (curTime > maxTime)
        {
            maxTime = curTime;
            rst.clear();
            rst.push_back(pre->val);
        }
        else if (curTime == maxTime)
        {
            rst.push_back(pre->val);
        }
        traverse(root->right);
    }
public:
    vector<int> findMode(TreeNode* root) {
        traverse(root);
        return rst;
    }
};

迭代

class Solution {
public:
    vector<int> findMode(TreeNode* root) {
        vector<int> rst;
        int maxTime = 0, curTime = 0;
        stack<TreeNode*> stk;
        TreeNode *cur = root, *pre = nullptr;

        while (cur || !stk.empty())
        {
            if (cur)
            {
                stk.push(cur);
                cur = cur->left;
            }
            else 
            {
                cur = stk.top();
                stk.pop();
                if (pre)
                {
                    if (pre->val == cur->val)
                    {
                        curTime++;
                    }
                    else
                    {
                        curTime = 1;
                    }
                }
                else
                {
                    curTime = 1;
                }
                pre = cur;
                if (curTime > maxTime)
                {
                    maxTime = curTime;
                    rst.clear();
                    rst.push_back(cur->val);
                }
                else if (curTime == maxTime)
                {
                    rst.push_back(cur->val);
                }
                cur = cur->right;
            }
        }

        return rst;
    }
};

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

偷偷看了一点提示,应该是用后序遍历,先处理子树,再到根节点,如果两棵子树返回包含两个目标节点的提示,该节点就是公共祖先节点

(要能想到是后序遍历,思路就打开了)

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root) return nullptr;
        TreeNode *leftRst = lowestCommonAncestor(root->left, p, q);
        TreeNode *rightRst = lowestCommonAncestor(root->right, p, q);
        
        if (root == p || root == q) // 如果根节点是p或q其中一个,可以直接返回
        {
            return root;
        }

        if (leftRst && rightRst) // 如果左右子树都不为空,那么该节点必定为最近公共祖先节点
        {
            return root;
        }

        return leftRst ? leftRst : rightRst; // 左子树不为空则返回左子树,否则不管右子树是否为空,都返回
    }
};

上面的代码是简化后的版本,隐藏了很多思考的细节,下面贴一下我按照自己的思路写的第一个版本文章来源地址https://www.toymoban.com/news/detail-579888.html

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root) return nullptr;
        TreeNode *leftRst = lowestCommonAncestor(root->left, p, q);
        TreeNode *rightRst = lowestCommonAncestor(root->right, p, q);

        if (!leftRst && !rightRst) // 如果左右子树都为空
        {
            if (root == p) // 根节点恰好是q或者p,可以返回根节点
            {
                return p;
            }
            else if (root == q)
            {
                return q;
            }
            else return nullptr; // 如果都不是,也要返回空
        }

        if (leftRst && rightRst) // 如果左右子树都不为空,那么该节点必定为最近公共祖先节点
        {
            return root;
        }

        if (root == p || root == q) // 如果根节点是p或者q中的一个,返回根节点
        {
            return root;
        }

        return leftRst ? leftRst : rightRst; // 返回q和p中不是空的那个节点
    }
    // 以上所有的可能情况都被一一列举出来,比较方便理解
};

到了这里,关于算法刷题Day 21 二叉搜索树的最小绝对差+二叉搜索树中的众数+二叉树的最近公共祖先的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包