题目

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

  • 结点左子树中所含节点的值 小于等于 当前节点的值
  • 结点右子树中所含节点的值 大于等于 当前节点的值

  • 左子树和右子树都是二叉搜索树


    示例 1：
    image.png

    1. 输入：root = [1,null,2,2]
    2. 输出：[2]

    示例 2：

    1. 输入：root = [0]
    2. 输出：[0]

提示：

  • 树中节点的数目在范围 [1, 10^4] 内
  • -10^5 <= Node.val <= 10^5

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

解题方法

递归

通过递归中序遍历二叉树，保证遍历数组升序。记录当前数字出现频率，最大频率。使用数组记录当前出现频率最大的所有数字，当出现频率更大的数出现时，清空数组，再保存当前频率下的所有数字。
时间复杂度O(n)，空间复杂度O(n)
C++代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    int pre = INT_MIN;
    int count = 0;
    int maxcount = 0;
    vector<int> result;
public:
    vector<int> findMode(TreeNode* root) {
        if(root->left)  findMode(root->left);

        if(pre==root->val) {
            count++;
        }
        else {
            pre = root->val;
            count = 1;
        }
        if(count==maxcount) {
            result.push_back(root->val);
        }
        if(count>maxcount) {
            result.clear();
            result.push_back(root->val);
            maxcount = count;
        }

        if(root->right) findMode(root->right);

        return result;
    }
};

Morris 遍历

通过 Morris 中序遍历二叉树，降低空间复杂度。（在遍历中直接更新比定义update函数更快）
时间复杂度O(n)，空间复杂度O(1)
C++代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    int pre = INT_MIN;
    int count = 0;
    int maxcount = 0;
    vector<int> result;
public:
    void update(int val) {
        if(pre==val) {
            count++;
        }
        else {
            pre = val;
            count = 1;
        }
        if(count==maxcount) {
            result.push_back(val);
        }
        if(count>maxcount) {
            result.clear();
            result.push_back(val);
            maxcount = count;
        }
    }

    vector<int> findMode(TreeNode* root) {
        TreeNode* cur = root;
        TreeNode* mostright;
        while(cur) {
            mostright = cur->left;
            if(mostright) {
                while(mostright->right && mostright->right!=cur)    mostright = mostright->right;
                if(!mostright->right) {
                    mostright->right = cur;
                    cur = cur->left;
                }
                else {
                    mostright->right = NULL;
                    //update(cur->val);
                    if(pre==cur->val)   count++;
                    else {
                        pre = cur->val;
                        count = 1;
                    }
                    if(count==maxcount) result.push_back(cur->val);
                    if(count>maxcount) {
                        result.clear();
                        result.push_back(cur->val);
                        maxcount = count;
                    }

                    cur = cur->right;
                }
            }
            else {
                //update(cur->val);
                if(pre==cur->val)   count++;
                else {
                    pre = cur->val;
                    count = 1;
                }
                if(count==maxcount) result.push_back(cur->val);
                if(count>maxcount) {
                    result.clear();
                    result.push_back(cur->val);
                    maxcount = count;
                }

                cur = cur->right;
            }
        }
        return result;
    }
};