[leetcode]: 501. Find Mode in Binary Search Tree

红太狼 2022-06-15 05:26 166阅读 0赞

# 1.题目 #

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\].

给一棵二叉搜索树，有重复元素。找出其中重复次数最多的元素。如果有多个重复次数一样的元素，则放在一个列表中作为返回结果。

# 2.分析 #

这题考察的是BST的中序遍历，中序遍历的元素是有序的，在遍历的过程中统计元素出现的次数即可。

# 3.代码 #

中序遍历–迭代

/**
     * 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) {
            vector<int> mode;
            if (root == NULL)
                return mode;
            int max_c = -1;//记录历史最多出现次数
            int last_v = INT_MIN;
            int count = 1;//当前值出现的次数
            stack<TreeNode*> nodes;
            while (!nodes.empty() || root) {
                if (root) {
                    nodes.push(root);
                    root = root->left;//先遍历到左子树最下边
                }
                else {
                    root = nodes.top();
                    nodes.pop();
                    if (last_v != INT_MIN) {
                        if (root->val == last_v)
                            ++count;
                        else
                            count = 1;
                    }
                    if (count > max_c)
                    {
                        max_c = count;
                        mode.erase(mode.begin(), mode.end());
                        mode.push_back(root->val);
                    }
                    else if (count == max_c)
                        mode.push_back(root->val);
                    last_v = root->val;
                    root = root->right;//转到右子树
                }
            }
            return mode;
        }
    };

中序遍历–递归

class Solution {
    public:
        void inOrder(TreeNode* root, vector<int>&mode,int& val,int& count,int& maxc) {
            if (root == NULL)
                return;
            inOrder(root->left,mode,val,count,maxc);
            if (val != INT_MIN) {
                if (val == root->val)
                    ++count;
                else
                    count = 1;
            }
            if (count > maxc) {
                maxc = count;
                mode.erase(mode.begin(), mode.end());//出现次数更多的元素，清空容器
                mode.push_back(root->val);
            }
            else if (count == maxc)
                mode.push_back(root->val);
            val = root->val;
            inOrder(root->right, mode, val, count, maxc);
        }
        vector<int> findMode(TreeNode* root) {
            vector<int> mode;
            if (root == NULL)
                return mode;
            int maxc = -1;
            int count = 1;
            int val = INT_MIN;
            inOrder(root, mode, val, count, maxc);
            return mode;
        }
    };