欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode 501——二叉搜索树中的众数

程序员文章站 2022-05-20 16:32:51
...

一、题目介绍

给定一个有相同值的二叉搜索树(BST),找出 BST 中的所有众数(出现频率最高的元素)。

假定 BST 有如下定义:

结点左子树中所含结点的值小于等于当前结点的值
结点右子树中所含结点的值大于等于当前结点的值
左子树和右子树都是二叉搜索树

例如:
给定 BST [1,null,2,2],

   1
    \
     2
    /
   2
返回[2].

提示:如果众数超过1个,不需考虑输出顺序

进阶:你可以不使用额外的空间吗?(假设由递归产生的隐式调用栈的开销不被计算在内)

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/find-mode-in-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

二、解题思路

参考官方题解,使用Mirrors中序遍历的方法。该方法的重点是为当前节点cur建立前驱节点pre,根据中序遍历的特点(先遍历左子树,再遍历当前节点,左后在遍历右子树),需将当前节点的左子树中最右边的节点(即中序遍历最后访问到的节点)设置为前驱节点,并且令pre->right = cur。这样当遍历完当前节点的左子树时,可以通过pre访问到cur。具体实现流程如下:

Morris 中序遍历的一个重要步骤就是寻找当前节点的前驱节点,并且 Morris 中序遍历寻找下一个点始终是通过转移到right 指针指向的位置来完成的。

  1. 如果当前节点没有左子树,则遍历这个点,然后跳转到当前节点的右子树。
  2. 如果当前节点有左子树,那么它的前驱节点一定在左子树上,我们可以在左子树上一直向右行走,找到当前点的前驱节点。

            (1)如果前驱节点没有右子树,就将前驱节点的right 指针指向当前节点。这一步是为了在遍历完前驱节点后能找到前驱节点的后继,也就是当前节点。
            (2)如果前驱节点的右子树为当前节点,说明前驱节点已经被遍历过并被修改了right 指针,这个时候我们重新将前驱的右孩子设置为空,遍历当前的点,然后跳转到当前节点的右子树。

三、解题代码

/**
 * 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:
    int count = 0, maxCount = 0, base;
    vector<int> res;
    void update(int val)
    {
        if(val == base)
            count++;
        else
        {
            count = 1; //更新计数
            base = val;//更新记录的值            
        }
        if(count == maxCount)
        {
            res.push_back(base);
        }
        else if(count > maxCount)
        {
            maxCount = count;
            res = vector<int> {base};
        }
    }

    vector<int> findMode(TreeNode* root) {
        //mirrors中序遍历
        TreeNode* cur = root;
        TreeNode* pre = NULL;
        while(cur)
        {
            if(!cur->left) //如果当前节点的左子树为空
            {
                update(cur->val); //遍历当前节点
                cur = cur->right; //开始访问当前节点的右子树
                continue;
            }
            //当前节点左子树不为空时
            pre = cur->left; //需要在当前节点的左子树中寻找其前驱节点
            while(pre->right && pre->right != cur) //在当前节点的左子树的右下边找其前驱节点
                pre = pre->right;
            if(!pre->right)
            {
                pre->right = cur;
                cur = cur->left;
            }
            else
            {
                pre->right = NULL;
                update(cur->val);
                cur = cur->right;
            }
        }
        return res;
    }
};

四、解题结果

LeetCode 501——二叉搜索树中的众数

相关标签: LeetCode刷题