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],

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日星期四