[LeetCode] Find Mode in Binary Search Tree 找二分搜索数的众数

简介:

Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST.

Assume a BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than or equal to the node's key.
  • The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
  • Both the left and right subtrees must also be binary search trees.

For example:

Given BST [1,null,2,2],

   1
    \
     2
    /
   2

return [2].

Note: If a tree has more than one mode, you can return them in any order.

Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).

这道题让我们求二分搜索树中的众数,这里定义的二分搜索树中左根右结点之间的关系是小于等于的,有些题目中是严格小于的,所以一定要看清题目要求。所谓的众数就是出现最多次的数字,可以有多个,那么这道题比较直接点思路就是利用一个哈希表来记录数字和其出现次数之前的映射,然后维护一个变量mx来记录当前最多的次数值,这样在遍历完树之后,根据这个mx值就能把对应的元素找出来。那么用这种方法的话就不需要用到二分搜索树的性质了,随意一种遍历方式都可以,下面我们来看递归的中序遍历的解法如下:

解法一:

class Solution {
public:
    vector<int> findMode(TreeNode* root) {
        vector<int> res;
        int mx = 0;
        unordered_map<int, int> m; 
        inorder(root, m, mx);
        for (auto a : m) {
            if (a.second == mx) {
                res.push_back(a.first);
            }
        }
        return res;
    }
    void inorder(TreeNode* node, unordered_map<int, int>& m, int& mx) {
        if (!node) return;
        inorder(node->left, m, mx);
        mx = max(mx, ++m[node->val]);
        inorder(node->right, m, mx);
    }
};

下面这种解法是上面方法的迭代形式,也是用的中序遍历的方法,有兴趣的童鞋可以实现其他的遍历方法:

解法二:

class Solution {
public:
    vector<int> findMode(TreeNode* root) {
        if (!root) return {};
        vector<int> res;
        TreeNode *p = root;
        stack<TreeNode*> s;
        unordered_map<int, int> m;
        int mx = 0;
        while (!s.empty() || p) {
            while (p) {
                s.push(p);
                p = p->left;
            }
            p = s.top(); s.pop();
            mx = max(mx, ++m[p->val]);
            p = p->right;
        }
        for (auto a : m) {
            if (a.second == mx) {
                res.push_back(a.first);
            }
        }
        return res;
    }
};

题目中的follow up说了让我们不用除了递归中的隐含栈之外的额外空间,那么我们就不能用哈希表了,不过这也不难,由于是二分搜索树,那么我们中序遍历出来的结果就是有序的,这样我们只要比较前后两个元素是否相等,就等统计出现某个元素出现的次数,因为相同的元素肯定是都在一起的。我们需要一个结点变量pre来记录上一个遍历到的结点,然后mx还是记录最大的次数,cnt来计数当前元素出现的个数,我们在中序遍历的时候,如果pre不为空,说明当前不是第一个结点,我们和之前一个结点值比较,如果相等,cnt自增1,如果不等,cnt重置1。如果此时cnt大于了mx,那么我们清空结果res,并把当前结点值加入结果res,如果cnt等于mx,那我们直接将当前结点值加入结果res,然后mx赋值为cnt。最后我们要把pre更新为当前结点,参见代码如下:

解法三:

class Solution {
public:
    vector<int> findMode(TreeNode* root) {
        vector<int> res;
        int mx = 0, cnt = 1;
        TreeNode *pre = NULL;
        inorder(root, pre, cnt, mx, res);
        return res;
    }
    void inorder(TreeNode* node, TreeNode*& pre, int& cnt, int& mx, vector<int>& res) {
        if (!node) return;
        inorder(node->left, pre, cnt, mx, res);
        if (pre) {
            cnt = (node->val == pre->val) ? cnt + 1 : 1;
        }
        if (cnt >= mx) {
            if (cnt > mx) res.clear();
            res.push_back(node->val);
            mx = cnt;
        } 
        pre = node;
        inorder(node->right, pre, cnt, mx, res);
    }
};

下面这种方法是上面解法的迭代写法,思路基本相同,可以参考上面的讲解,参见代码如下:

解法四:

class Solution {
public:
    vector<int> findMode(TreeNode* root) {
        if (!root) return {};
        vector<int> res;
        TreeNode *p = root, *pre = NULL;
        stack<TreeNode*> s;
        int mx = 0, cnt = 1;;
        while (!s.empty() || p) {
            while (p) {
                s.push(p);
                p = p->left;
            }
            p = s.top(); s.pop();
            if (pre) {
                cnt = (p->val == pre->val) ? cnt + 1 : 1;
            }
            if (cnt >= mx) {
                if (cnt > mx) res.clear();
                res.push_back(p->val);
                mx = cnt;
            }
            pre = p;
            p = p->right;
        }
        return res;
    }
};

本文转自博客园Grandyang的博客,原文链接:Find Mode in Binary Search Tree 找二分搜索数的众数,如需转载请自行联系原博主。

相关文章
|
Java
Leetcode 114. Flatten Binary Tree to Linked List
思路也很简单,先把root的左子树(如有)变成单链表 leftlinkedlist,把root的右子树(如有)变成单链表 rightlinkedlist,再把root的右节点变成leftlikedlist,再把rightlinkedlist接到leftlinkedlist后面,代码如下。
40 1
Leetcode 74. Search a 2D Matrix
这道题很简单,为此专门写篇博客其实算博客凑数了。给你一个每一行每一列都是增序,且每一行第一个数都大于上一行末尾数的矩阵,让你判断某个数在这个矩阵中是否存在。 假设矩阵是m*n,扫一遍的时间复杂度就是O(m*n),题目中给出的这么特殊的矩阵,时间复杂度可以降到O(m+n),具体代码如下,写的比较挫。
83 1
|
Java
Leetcode 295. Find Median from Data Stream
在一个有序数组中找中位数,但需要支持再数组中添加新的元素。本来是有序里的,可以很轻易就查到中位数,但如果添加新数字后,不一定有序。如果先对数组排序,那代价就比较大了,每次排序时间复杂度O(n*log(n)),看discuss发现了一种很巧妙的解法,可以把添加数据的时间复杂度降低到O(log(n)) ,查询中位数O(1)。
51 0
Leetcode Minimum Depth of Binary Tree (面试题推荐)
计算树的最小深度 很简单的一道题,只需要遍历一次树,到叶子节点的时候计算一下深度和当前最小深度比较,保存最小值就行。 我在这用了一个全局变量 mindepth。总感觉我这代码写的不够简练,求更精简的方法。
44 0
Leetcode Binary Tree Postorder Traversal(面试题推荐)
非递后续归遍历二叉树,肯定得用到栈。先序遍历很好写,但后续遍历就不是那么容易了。 只需要设置个指针pre,指向最后输出的那个节点就行了,只要判断cur指针指向的是上次输出节点的父节点,且cur无其他未遍历的节点,这个时候就把cur节点输出即可,然后更改pre。原理是要遍历当前节点,其所有子节点都必须遍历完,因为肯定是先左后右,所以只需一个指针保持前一次输出的结果即可。
50 0
代码随想录Day17 LeetCode T98 验证二叉搜索树 T530 二叉搜索树的最小绝对差 T501 二叉搜索树中的众数 T236二叉搜索树的最近公共祖先
代码随想录Day17 LeetCode T98 验证二叉搜索树 T530 二叉搜索树的最小绝对差 T501 二叉搜索树中的众数 T236二叉搜索树的最近公共祖先
55 0
Leetcode 236. Lowest Common Ancestor of a Binary Tree
根据LCA的定义,二叉树中最小公共祖先就是两个节点p和q最近的共同祖先节点,LCA的定义没什么好解释的,主要是这道题的解法。
36 0
|
19天前
【LeetCode 42】501.二叉搜索树中的众数
【LeetCode 42】501.二叉搜索树中的众数
8 0
|
6月前
leetcode501二叉搜索树中的众数刷题打卡
leetcode501二叉搜索树中的众数刷题打卡
25 0
|
6月前
|
Java C++ Python
leetcode-501:二叉搜索树中的众数
leetcode-501:二叉搜索树中的众数
35 0