题目

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

假定 BST 有如下定义:

结点左子树中所含结点的值小于等于当前结点的值
结点右子树中所含结点的值大于等于当前结点的值
左子树和右子树都是二叉搜索树
例如:
给定 BST [1,null,2,2],

image.png

返回[2].

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

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/find-mode-in-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解答

使用额外空间map的方法

  1. var findMode = function(root) {
  2. // 使用递归中序遍历
  3. let map = new Map();
  4. // 1. 确定递归函数以及函数参数
  5. const traverTree = function(root) {
  6. // 2. 确定递归终止条件
  7. if(root === null) {
  8. return ;
  9. }
  10. traverTree(root.left);
  11. // 3. 单层递归逻辑
  12. map.set(root.val,map.has(root.val)?map.get(root.val)+1:1);
  13. traverTree(root.right);
  14. }
  15. traverTree(root);
  16. //上面把数据都存储到map
  17. //下面开始寻找map里面的
  18. // 定义一个最大出现次数的初始值为root.val的出现次数
  19. let maxCount = map.get(root.val);
  20. // 定义一个存放结果的数组res
  21. let res = [];
  22. for(let [key,value] of map) {
  23. // 如果当前值等于最大出现次数就直接在res增加该值
  24. if(value === maxCount) {
  25. res.push(key);
  26. }
  27. // 如果value的值大于原本的maxCount就清空res的所有值,因为找到了更大的
  28. if(value>maxCount) {
  29. res = [];
  30. maxCount = value;
  31. res.push(key);
  32. }
  33. }
  34. return res;
  35. };

不使用额外空间,利用二叉树性质,中序遍历(有序):

既然是搜索树,它中序遍历就是有序的
image.png
中序遍历

  1. const travelTree = function(cur) {
  2. if (cur == null) return ;
  3. travelTree(cur.left); // 左
  4. (处理节点) // 中
  5. travelTree(cur.right); // 右
  6. return ;
  7. }

作比较的话就是弄一个指针指向前一个节点,这样每次cur(当前节点)才能和pre(前一个节点)作比较。
而且初始化的时候pre = NULL,这样当pre为NULL时候,我们就知道这是比较的第一个元素。

  1. if(pre.val === cur.val) {
  2. count++;
  3. }else {
  4. count = 1;
  5. }
  6. pre = cur;
  7. if(count === maxCount) {
  8. res.push(cur.val);
  9. }
  10. if(count > maxCount) {
  11. res = [];
  12. maxCount = count;
  13. res.push(cur.val);
  14. }
  15. }

完整代码

  1. var findMode = function(root) {
  2. // 不使用额外空间,使用中序遍历,设置出现最大次数初始值为1
  3. let count = 0,maxCount = 1;
  4. let pre = root,res = [];
  5. // 1.确定递归函数及函数参数
  6. const travelTree = function(cur) {
  7. // 2. 确定递归终止条件
  8. if(cur === null) {
  9. return ;
  10. }
  11. travelTree(cur.left);
  12. // 3. 单层递归逻辑
  13. if(pre.val === cur.val) {
  14. count++;
  15. }else {
  16. count = 1;
  17. }
  18. pre = cur;
  19. if(count === maxCount) {
  20. res.push(cur.val);
  21. }
  22. if(count > maxCount) {
  23. res = [];
  24. maxCount = count;
  25. res.push(cur.val);
  26. }
  27. travelTree(cur.right);
  28. }
  29. travelTree(root);
  30. return res;
  31. };