MENU

LeetCode501. Find Mode in Binary Search Tree(二分搜索树 / 模拟)

2019 年 03 月 14 日 • 阅读: 944 • LeetCode阅读设置

LeetCode501. Find Mode in Binary Search Tree(二分搜索树 / 模拟)

  • Easy
  • Accepted:51,648
  • Submissions:132,574

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).


链接

https://leetcode.com/problems/find-mode-in-binary-search-tree

题意

给定一个带有相同元素的二分搜索树,找到其中出现次数最多的元素(可能有多个)。输出顺序不唯一。

题解

考虑二分搜索树本身的特点:对于根结点,其左子树的结点的值都小于等于它,其右子树的结点的值都大于等于它,因此我们可以对其做一个中序遍历,那么我们得到的结点值就是一个有序序列,于是问题就变成了从一个有序序列中找出现次数最多的元素。

但是实际上我们每次只能访问一个元素,所以我们需要使用三个变量curVal,tmpCnt,maxCnt分别记录当前结点值,该结点出现的次数以及最大次数,使用vector来保存答案。

然后在中序遍历的过程中,我们需要判断curVal是否等于root->val,如果不等我们就需要把tmpCnt置1,对新的结点值计数,然后判断tmpCnt与maxCnt的大小关系,如果tmpCnt大于maxCnt那么就更新maxCnt,并把vector清空再记录curVal,如果等于那么就直接加入到vector中即可。

至于时间复杂度,我们会遍历所有的结点,对于每个结点做常数级的处理,因此平均复杂度是$O(n)$。

代码

  • Runtime: 28 ms, faster than 98.44% of C++ online submissions for Find Mode in Binary Search Tree.
  • Memory Usage: 23.5 MB, less than 59.22% of C++ online submissions for Find Mode in Binary Search Tree.
/**
 * 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:
    vector<int> findMode(TreeNode* root) {
        inorder(root);
        return ans;
    }

private:
    vector <int> ans;
    int maxCnt = 0, tmpCnt = 0, curVal; // 出现最大次数,当前元素出现次数,当前元素
    void inorder(TreeNode* root)
    {
        if (root == NULL)
            return ;
        inorder(root->left);
        ++tmpCnt;
        if (curVal != root->val) // 不为同一个值,更新
        {
            curVal = root->val;
            tmpCnt = 1;
        }
        if (tmpCnt > maxCnt) // 更新maxCnt
        {
            maxCnt = tmpCnt;
            ans.clear();
            ans.push_back(curVal);
        }
        else if (tmpCnt == maxCnt) // 多个maxCnt
            ans.push_back(curVal);
        inorder(root->right);
    }
};

参考

https://blog.csdn.net/liuchuo/article/details/54854037


The end.
2019年3月14日 星期四
最后编辑于: 2019 年 03 月 15 日