二叉搜索树中的众数

646 次访问 2020-11-01

Walker

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

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

提示：如果众数超过1个，不需考虑输出顺序
进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）

自我解答

使用 map 记录每个数量，不过使用额外空间了

class Solution:

    def findMode(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        cal_map = {}
        self.calvalues(root, cal_map)
        m = max(cal_map.values())
        return filter(lambda key: cal_map[key] == m, cal_map.keys())

    def calvalues(self, node: TreeNode, cal_map):
        if not node:
            return
        self.calvalues(node.left, cal_map)
        self.calvalues(node.right, cal_map)
        if node.val not in cal_map:
            cal_map[node.val] = 1
        else:
            cal_map[node.val] += 1

题解

这里是不清楚二叉搜索树(也叫二叉排序树)，如题意中描述的那样，这种结构就是二叉排序树，
最显著的特点是其中序遍历序列实际上是一个从小到大排列的数组。

class Solution2:

    def findMode(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        self.modes = []
        self.maxv = 0
        self.thisv = 0
        self.this_val = None
        self.last_val = None
        self.in_order(root)
        if self.thisv == self.maxv:
            self.modes.append(self.last_val)
        elif self.thisv > self.maxv:
            self.modes = [self.this_val]

        return self.modes

    def in_order(self, node: TreeNode):
        if not node:
            return
        self.in_order(node.left)

        self.this_val = node.val
        if self.last_val is None:
            self.last_val = self.this_val
            self.thisv = 1
        elif self.last_val == self.this_val:
            self.thisv += 1
        else:
            if self.thisv == self.maxv:
                self.modes.append(self.last_val)
            elif self.thisv > self.maxv:
                self.modes = [self.last_val, ]
                self.maxv = self.thisv
            self.last_val = self.this_val
            self.thisv = 1

        self.in_order(node.right)

原题链接：https://leetcode-cn.com/problems/find-mode-in-binary-search-tree