题目

题目来源：力扣（LeetCode）

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

假定 BST 有如下定义：

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

1
\
2
/
2

返回[2].

思路分析

中序遍历

二叉搜索树的中序遍历结果是一个升序序列，那么在序列中重复出现的数字一定是连续出现的。

  1.   1<br />    /   \<br />   0     2<br />  / \    /<br />-1   0  2

例如上面的二叉搜索的中序遍历序列是 [-1, 0, 0, 1, 2, 2] ，序列中的 0 和 2 是重复出现的，并且所有的 0 都集中在一个连续的段内，所有的 2 也集中在一个连续的段内。

因此我们可以在中序遍历的过程中，对遍历到的当前元素进行处理。使用 base 记录当前遍历的数字，用 count 记录当前数字重复的次数，用 maxCount 来维护已经扫描过的数当中出现最多的那个数字的出现次数，用 answer 数组记录出现的众数。每次遍历到一个新的元素时：

  • 首先更新 base 和 count:
    • 如果该元素和 base 相等，那么 count 自增 1；
    • 否则将 base 更新为当前数字，count 复位为 1。
  • 然后更新 maxCount：
    • 如果 count=maxCount，那么说明当前的这个数字（base）出现的次数等于当前众数出现的次数，将 base 加入 answer 数组；
    • 如果 count>maxCount，那么说明当前的这个数字（base）出现的次数大于当前众数出现的次数，因此，我们需要将 maxCount 更新为 count，清空 answer 数组后将base 加入answer 数组。

代码

  1. /**
  2.  * Definition for a binary tree node.
  3.  * function TreeNode(val, left, right) {
  4.  *     this.val = (val===undefined ? 0 : val)
  5.  *     this.left = (left===undefined ? null : left)
  6.  *     this.right = (right===undefined ? null : right)
  7.  * }
  8.  */
  9. /**
  10.  * @param {TreeNode} root
  11.  * @return {number[]}
  12.  */
  13. var findMode = function (root) {
  14.   // 记录当前遍历的数字
  15.   let base = 0;
  16.   // 记录当前遍历数字重复的次数
  17.   let count = 0;
  18.   // 维护已经遍历过的数当中出现最多的那个数字的出现次数
  19.   let maxCount = 0;
  20.   // 记录出现的众数
  21.   let answer = [];
  23.   // 每次遍历到一个数时更新维护上面的四个变量
  24.   const update = (x) => {
  25.     // 如果当前遍历的数字与已经遍历过的某个数字相同，则 count 自增 1
  26.     if (x === base) {
  27.       ++count;
  28.     } else {
  29.       // 如果当前遍历的数字是一个新的数字，则将 base 更新为当期的数字，count 重置为 1
  30.       count = 1;
  31.       base = x;
  32.     }
  34.     // 如果当前数字重复的次数与出现最多的那个数字的出现次数相等，将 base 加入 answer 数组
  35.     if (count === maxCount) {
  36.       answer.push(base);
  37.     }
  38.     // 如果当前数字重复的次数大于出现最多的那个数字的出现次数，即 count > maxCount
  39.     // 将 maxCount 重置为 count，并且清空answer 数组后将 base 加入 answer 数组
  40.     if (count > maxCount) {
  41.       maxCount = count;
  42.       answer = [base];
  43.     }
  44.   }
  46.   // 递归中序遍历二叉搜索树
  47.   const dfs = (node) => {
  48.     if (!node) {
  49.       return;
  50.     }
  51.     // 遍历左子树
  52.     dfs(node.left);
  53.     // 遍历根节点(在这里对当前节点进行处理)
  54.     update(node.val);
  55.     // 遍历右子树
  56.     dfs(node.right);
  57.   }
  59.   dfs(root);
  60.   return answer;
  61. };

Morris 中序遍历

Morris 中序遍历的一个重要步骤就是寻找当前节点的前驱节点，并且 Morris 中序遍历寻找下一个点始终是通过转移到 right 指针指向的位置来完成的。

morris遍历的实现原则

记当前节点为cur：

  1. 如果cur无左孩子，cur向右移动（cur=cur.right）
  2. 如果cur有左孩子，找到cur左子树上最右的节点，记为mostright
    1. 如果mostright的right指针指向空，让其指向cur，cur向左移动（cur=cur.left）
    2. 如果mostright的right指针指向cur，让其指向空，cur向右移动（cur=cur.right）

实现以上的原则，即实现了morris遍历。

  1. var findMode = function(root) {
  2.     let base = 0, count = 0, maxCount = 0;
  3.     let answer = [];
  5.     const update = (x) => {
  6.         if (x === base) {
  7.             ++count;
  8.         } else {
  9.             count = 1;
  10.             base = x;
  11.         }
  12.         if (count === maxCount) {
  13.             answer.push(base);
  14.         }
  15.         if (count > maxCount) {
  16.             maxCount = count;
  17.             answer = [base];
  18.         }
  19.     }
  21.     let cur = root, pre = null;
  22.     while (cur !== null) {
  23.         if (cur.left === null) {
  24.             update(cur.val);
  25.             cur = cur.right;
  26.             continue;
  27.         }
  28.         pre = cur.left;
  29.         while (pre.right !== null && pre.right !== cur) {
  30.             pre = pre.right;
  31.         }
  32.         if (pre.right === null) {
  33.             pre.right = cur;
  34.             cur = cur.left;
  35.         } else {
  36.             pre.right = null;
  37.             update(cur.val);
  38.             cur = cur.right;
  39.         }
  40.     }
  41.     return answer;
  42. };

morris 遍历参考：
https://zhuanlan.zhihu.com/p/101321696 https://blog.csdn.net/yangfeisc/article/details/45673947 https://www.zhihu.com/zvideo/1399844310284697600 https://www.jianshu.com/p/959247c29a7b