0501. 二叉搜索树中的众数【简单】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 普通中序遍历
• 3. 🎯 s.2 - Morris 遍历
• 4. Morris 遍历是什么？
• 5. 🔗 引用

1. 📝 题目描述

• leetcode

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

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

假定 BST 满足如下定义：

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

---

示例 1：

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

---

示例 2：

输入：root = [0]
输出：[0]

---

提示：

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

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

2. 🎯 s.1 - 普通中序遍历

c

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* modes = NULL;
int modesSize = 0;
int maxCount = 0;
int currentCount = 0;
int prevVal = 0;
bool hasPrev = false;

void inorder(struct TreeNode* node) {
    if (!node)
        return;

    inorder(node->left);

    if (!hasPrev || node->val != prevVal) {
        currentCount = 1;
    } else {
        currentCount++;
    }
    hasPrev = true;

    if (currentCount > maxCount) {
        maxCount = currentCount;
        modesSize = 0;
        modes[modesSize++] = node->val;
    } else if (currentCount == maxCount) {
        modes[modesSize++] = node->val;
    }

    prevVal = node->val;
    inorder(node->right);
}

int* findMode(struct TreeNode* root, int* returnSize) {
    modes = (int*)malloc(sizeof(int) * 10000);
    modesSize = 0;
    maxCount = 0;
    currentCount = 0;
    hasPrev = false;

    inorder(root);
    *returnSize = modesSize;
    return modes;
}

js

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var findMode = function (root) {
  let modes = []
  let prev = null
  let count = 0
  let maxCount = 0

  // 中序遍历函数
  function inorder(node) {
    if (!node) return

    // 遍历左子树
    inorder(node.left)

    // 处理当前节点
    if (prev === null || node.val !== prev) {
      count = 1
    } else {
      count++
    }

    // 更新众数列表
    if (count > maxCount) {
      maxCount = count
      modes = [node.val]
    } else if (count === maxCount) {
      modes.push(node.val)
    }

    prev = node.val

    // 遍历右子树
    inorder(node.right)
  }

  inorder(root)
  return modes
}

py

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findMode(self, root: Optional[TreeNode]) -> list[int]:
        modes = []
        self.prev = None
        self.count = 0
        self.max_count = 0

        def inorder(node):
            if not node:
                return
            inorder(node.left)

            if self.prev is None or node.val != self.prev:
                self.count = 1
            else:
                self.count += 1

            if self.count > self.max_count:
                self.max_count = self.count
                modes.clear()
                modes.append(node.val)
            elif self.count == self.max_count:
                modes.append(node.val)

            self.prev = node.val
            inorder(node.right)

        inorder(root)
        return modes

• 时间复杂度：$O(n)$，其中 n 是二叉搜索树的节点数，需要遍历每个节点一次
• 空间复杂度：$O(h)$，其中 h 是二叉搜索树的高度，递归调用栈的深度。平均情况下为 $O(\log n)$，最坏情况下为 $O(n)$

算法思路：

• BST 的中序遍历产生有序序列，相同值必然相邻，因此可以在一次遍历中统计连续相同值的出现次数
• 维护 prev（前一个节点值）、count（当前值的连续出现次数）、maxCount（已知的最大出现次数）和 modes（众数列表）
• 中序遍历每个节点时：
  • 若当前值与 prev 不同，重置 count = 1；否则 count++
  • 若 count > maxCount，清空 modes 并加入当前值；若 count === maxCount，追加当前值
• 遍历结束后 modes 即为所有众数

3. 🎯 s.2 - Morris 遍历

c

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* modes = NULL;
int modesSize = 0;
int maxCount = 0;
int currentCount = 0;
int prevVal = 0;
bool hasPrev = false;

void handleValue(int val) {
    if (!hasPrev || val != prevVal) {
        currentCount = 1;
    } else {
        currentCount++;
    }
    hasPrev = true;

    if (currentCount > maxCount) {
        maxCount = currentCount;
        modesSize = 0;
        modes[modesSize++] = val;
    } else if (currentCount == maxCount) {
        modes[modesSize++] = val;
    }
    prevVal = val;
}

int* findMode(struct TreeNode* root, int* returnSize) {
    modes = (int*)malloc(sizeof(int) * 10000);
    modesSize = 0;
    maxCount = 0;
    currentCount = 0;
    hasPrev = false;

    struct TreeNode* current = root;
    while (current) {
        if (!current->left) {
            handleValue(current->val);
            current = current->right;
        } else {
            struct TreeNode* predecessor = current->left;
            while (predecessor->right && predecessor->right != current)
                predecessor = predecessor->right;

            if (!predecessor->right) {
                predecessor->right = current;
                current = current->left;
            } else {
                predecessor->right = NULL;
                handleValue(current->val);
                current = current->right;
            }
        }
    }

    *returnSize = modesSize;
    return modes;
}

js

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var findMode = function (root) {
  let modes = []
  let maxCount = 0
  let currentCount = 0
  let prevVal = null

  let current = root

  while (current !== null) {
    if (current.left === null) {
      // 【1】找到了未处理过的最左节点
      handleValue(current.val)
      current = current.right
    } else {
      // 找到当前节点的前驱节点
      let predecessor = current.left
      while (predecessor.right !== null && predecessor.right !== current) {
        predecessor = predecessor.right
      }

      if (predecessor.right === null) {
        // 利用空节点建立线索
        // 线索：记录的是处理完这个节点之后，下一个要处理的节点是谁
        predecessor.right = current
        current = current.left
      } else {
        // 恢复树结构
        predecessor.right = null
        // 【2】找到了下一个未处理过的最左节点
        handleValue(current.val)
        current = current.right
      }
    }
  }

  function handleValue(val) {
    // 更新当前值的计数
    if (prevVal === null || val !== prevVal) {
      currentCount = 1
    } else {
      currentCount++
    }

    // 更新众数列表
    if (currentCount > maxCount) {
      maxCount = currentCount
      modes = [val]
    } else if (currentCount === maxCount) {
      modes.push(val)
    }

    prevVal = val
  }

  return modes
}

py

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findMode(self, root: Optional[TreeNode]) -> list[int]:
        modes = []
        max_count = 0
        current_count = 0
        prev_val = None
        has_prev = False

        def handle_value(val):
            nonlocal current_count, max_count, prev_val, has_prev
            if not has_prev or val != prev_val:
                current_count = 1
            else:
                current_count += 1
            has_prev = True

            if current_count > max_count:
                max_count = current_count
                modes.clear()
                modes.append(val)
            elif current_count == max_count:
                modes.append(val)
            prev_val = val

        current = root
        while current:
            if not current.left:
                handle_value(current.val)
                current = current.right
            else:
                predecessor = current.left
                while predecessor.right and predecessor.right is not current:
                    predecessor = predecessor.right

                if not predecessor.right:
                    predecessor.right = current
                    current = current.left
                else:
                    predecessor.right = None
                    handle_value(current.val)
                    current = current.right

        return modes

• 时间复杂度：$O(n)$，需要遍历每个节点一次
• 空间复杂度：$O(1)$，只使用了常数个额外变量（不考虑结果数组）

算法思路：

• Morris 遍历利用叶子节点的空指针建立临时线索，从而在不使用栈的情况下实现中序遍历
• 核心逻辑：对于有左子树的节点，找到其左子树的最右节点（前驱节点），通过建立或断开线索来决定是继续深入左子树还是处理当前节点
• 统计众数的逻辑与 s.1 完全一致，只是遍历方式从递归改为 Morris，将空间复杂度从 $O(h)$ 降为 $O(1)$

4. Morris 遍历是什么？

Morris 遍历算法在知识库 TNotes.algorithms 中有记录 -> 0007. Morris 遍历。

5. 🔗 引用

• 众数 - 百度百科
• bilibili - 【Manim】Morris 中序遍历可视化
• 知乎 - 神级遍历——morris
• TNotes.algorithms - 0007. Morris 遍历