【LeetCode二叉树#15】二叉搜索树中的众数（递归中序遍历）

二叉搜索树中的众数

力扣题目链接(opens new window)

给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。

假定 BST 有如下定义：

结点左子树中所含结点的值小于等于当前结点的值
结点右子树中所含结点的值大于等于当前结点的值
左子树和右子树都是二叉搜索树

例如：

给定 BST [1,null,2,2],

501. 二叉搜索树中的众数

返回[2].

提示：如果众数超过1个，不需考虑输出顺序

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

思路

初见思路是：直接把二叉树遍历一遍，得到结果数组，在用map进行频率统计，返回出现最多的那个即可

但是，像上面这样处理的话，统计频率那块的代码不太好写（需要自定义比较函数）

所以还是用中序遍历+递归的方式去做

不同的是，这里也要引入二叉搜索树的最小绝对差中的双指针的技巧

即在遍历过程中设置两个指针，一个指向前一节点，一个指向当前节点

在本题中，通过前一节点与当前节点的比较，来判断一个元素是否出现了多次，并统计其出现次数

这里还需要设置两个计数变量，一个count用来记录当前遍历值的出现次数，一个maxCount用于记录出现过的最大count。

当需要更新maxCount时，同时记录下当前的节点值并清空上次记录的节点值。

代码分析

还是先写递归函数

因为我们要遍历 整颗二叉树 ，且不需要立刻返回判断值，所以递归函数的输入参数是根节点且没有返回值。根据递归的中序遍历不难写出以下代码：

//定义计数变量
int maxCount = 0;
int count = 0;
//定义前一节点指针
TreeNode* pre = NULL;

void searchBST(TreeNode* cur){
    //确定终止条件
    if(cur == NULL) return;
    //左
    searchBST(cur->left);
    //中，比较前一节点和当前节点并统计当前节点值的出现次数
    
    //右
    searchBST(cur->right);
    
    return;//void也要写return
}

在中的处理逻辑里，我们引入双指针

一共有下面3中情况需要count去记录

前一节点指针为空时，当前节点指针指向第一个节点，因此count需要记1
前一节点指针不为空时，且当前节点指针值与前一节点值不相等，count需要记1（当前遍历值只出现了一次）
当前节点指针值与前一节点值相等，count需要累加记录

当记录完成，更新当前节点与前一节点的指针即可

//定义计数变量
int maxCount = 0;
int count = 0;
//定义前一节点指针
TreeNode* pre = NULL;

void searchBST(TreeNode* cur){
    //左
    searchBST(cur->left);
    //中，比较前一节点和当前节点并统计当前节点值的出现次数
    if(pre == NULL){//当前节点指针指向第一个节点
        count = 1;
    }else if(pre->val == cur->val){//当前节点指针值与前一节点值相等
        count++;
    }else{//前一节点指针不为空时，且当前节点指针值与前一节点值不相等
        count = 1;
    }
    pre = cur;//更新当前节点与前一节点的指针
    
    //右
    searchBST(cur->right);
    
    return;//void也要写return
}

得到count之后，我们需要去更新maxCount，也有两种情况：

count与maxCount相同，说明有多个元素，它们都出现了多次并且次数相同（即多个众数的情况）
count大于maxCount，说明有某个元素的出现次数更多，该元素将成为新的众数

情况一种我们只需将当前遍历的节点的值再加入结果数组即可

情况二则需要先清空之前结果数组保存的值，再加入新的众数（即当前遍历的节点的值）

上述过程也在中的处理逻辑里完成

//定义计数变量
int maxCount = 0;
int count = 0;
//定义前一节点指针
TreeNode* pre = NULL;
//定义结果数组
vector<int> res;

void searchBST(TreeNode* cur){
    //左
    searchBST(cur->left);
    //中，比较前一节点和当前节点并统计当前节点值的出现次数
    if(pre == NULL){//当前节点指针指向第一个节点
        count = 1;
    }else if(pre->val == cur->val){//当前节点指针值与前一节点值相等
        count++;
    }else{//前一节点指针不为空时，且当前节点指针值与前一节点值不相等
        count = 1;
    }
    //比较并更新maxCount，记录结果值
    if(count == maxCount){//出现多个众数
        res.push_back(cur->val);
    }else if(count > maxCount){//出现新的众数
        //更新最大出现次数
        maxCount = count;
        //清空结果数组
        res.clear();
        //更新众数
        res.push_back(cur->val);
    }
    pre = cur;
    
    //右
    searchBST(cur->right);
    return;//void也要写return
}

完整代码

class Solution {
private:
    //定义计数变量
    int maxCount = 0;
    int count = 0;
    //定义前一节点指针
    TreeNode* pre = NULL;
    //定义结果数组
    vector<int> res;

    void searchBST(TreeNode* cur){
        //确定终止条件
        if(cur == NULL) return;
        //左
        searchBST(cur->left);
        //中，比较前一节点和当前节点并统计当前节点值的出现次数
        if(pre == NULL){//当前节点指针指向第一个节点
            count = 1;
        }else if(pre->val == cur->val){//当前节点指针值与前一节点值相等
            count++;
        }else{//前一节点指针不为空时，且当前节点指针值与前一节点值不相等
            count = 1;
        }
        pre = cur;

        //比较并更新maxCount，记录结果值
        if(count == maxCount){//出现多个众数
            res.push_back(cur->val);
        }else if(count > maxCount){//出现新的众数
            //更新最大出现次数
            maxCount = count;
            //清空结果数组
            res.clear();
            //更新众数
            res.push_back(cur->val);
        }
        //右
        searchBST(cur->right);
        return;//void也要写return
    }
public:
    vector<int> findMode(TreeNode* root) {
        //res.clear();//清理一下结果数组

        searchBST(root);//调用递归
        return res;//返回结果数组
    }
};