leetcode501. 二叉搜索树中的众数

leetcode501. 二叉搜索树中的众数

题目描述

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

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

假定 BST 满足如下定义：

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

示例 1：

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

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

提示：

树中节点的数目在范围 [1, 104] 内 -105 <= Node.val <= 105

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

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

解题思路

法1

中序遍历:
题目描述说:

结点左子树中所含节点的值 小于等于 当前节点的值

结点右子树中所含节点的值 大于等于 当前节点的值

所以在中序遍历的是否,就能够得到一个有序数组,相同的数据是在一起的,我们通过判断相同数据的个数确定该数是否为众数(个数>=最大的个数),

如果大于,之前的众数就不再是众数了,

如果等于,将次数值加到众数数组中

最后遍历完成输出众数数组

• 时间复杂度(O(n))
• 空间复杂度(O(n))

执行结果

法1

func inorderTraversalHelper(root *TreeNode, result *[]int) {
    if root == nil {
        return
    }
    inorderTraversalHelper(root.Left, result)
    *result = append(*result, root.Val)
    inorderTraversalHelper(root.Right, result)
}

func findMode(root *TreeNode) []int {
    a := []int{}
    inorderTraversalHelper(root, &a)
    i, j, m := 1, 0, 0
t := 0
    for ; i < len(a); i++ {
        if a[t] != a[i] {
            if m < i-t {
                m = i - t
                j = 1
                a[0] = a[t]
            } else if m == i-t {
                a[j] = a[t]
                j++
            }
            t = i
        }
    }
    if m < i-t {
        return []int{a[t]}
    } else if m == i-t {
        return append(a[:j], a[t])
    } else {
        return a[:j]
    }
}

执行结果： 通过 显示详情 查看示例代码 添加备注

执行用时： 8 ms , 在所有 Go 提交中击败了 83.39% 的用户 内存消耗： 5.7 MB , 在所有 Go 提交中击败了 99.45% 的用户 通过测试用例： 23 / 23

法2

法3