题目描述

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

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

假定 BST 满足如下定义：

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

示例 1：

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

示例 2：

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

提示：

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

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

解题思路

最直接的思路是遍历二叉树，统计每个节点的值出现的次数，然后找出出现次数最多的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
import "container/heap"

type IntHeap [][2]int

func (h IntHeap) Len() int {
	return len(h)
}

func (h IntHeap) Less(i, j int) bool {
	return h[i][1] > h[j][1]
}

func (h *IntHeap) Swap(i, j int) {
	(*h)[i], (*h)[j] = (*h)[j], (*h)[i]
}

func (h *IntHeap) Push(v interface{}) {
	*h = append(*h, v.([2]int))
}

func (h *IntHeap) Pop() interface{} {
	res := (*h)[len(*h)-1]
	*h = (*h)[:len(*h)-1]
	return res
}

func findMode(root *TreeNode) []int {
	m := make(map[int]int)
	var dfs func(node *TreeNode)
	dfs = func(node *TreeNode) {
		if node == nil {
			return
		}

		dfs(node.Left)
		m[node.Val]++
		dfs(node.Right)
	}
	dfs(root)

	h := make(IntHeap, len(m))
	heap.Init(&h)
	for n, cnt := range m {
		heap.Push(&h, [2]int{n, cnt})
	}

	ans := []int{}
	for maxCnt := 0; h.Len() > 0; {
		if x := heap.Pop(&h).([2]int); x[1] < maxCnt {
			break
		} else {
			ans = append(ans, x[0])
			maxCnt = x[1]
		}
	}

	return ans
}

这种方法的时间复杂度是 O(n log n)，空间复杂度是 O(n)，因为我们需要存储每个节点的值和它出现的次数，并且需要对最后的结果进行排序。

考虑可以在遍历的时候更新当前出现次数最多的值，这样就可以将时间复杂度优化到 O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findMode(root *TreeNode) []int {
	m := make(map[int]int)
	mFreq := 0
	var dfs func(node *TreeNode)
	dfs = func(node *TreeNode) {
		if node == nil {
			return
		}

		dfs(node.Left)
		m[node.Val]++
		mFreq = max(m[node.Val], mFreq)
		dfs(node.Right)
	}
	dfs(root)

	ans := []int{}
	for n, freq := range m {
		if freq == mFreq {
			ans = append(ans, n)
		}
	}

	return ans
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

这种方法的时间复杂度是 O(n)，空间复杂度也是 O(n)，因为我们需要存储每个节点的值和它出现的次数。并且 前、中、后序遍历的方式都可以实现。

更进一步，我们可以在遍历的过程中维护一个前一个节点的值和当前出现次数最多的值，这样就可以不使用额外的空间（假设由递归产生的隐式调用栈的开销不被计算在内），并且在一次遍历中完成所有操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findMode(root *TreeNode) []int {
	m := make(map[int]int)
	mFreq := 0
	var dfs func(node *TreeNode)
	dfs = func(node *TreeNode) {
		if node == nil {
			return
		}

		dfs(node.Left)
		m[node.Val]++
		mFreq = max(m[node.Val], mFreq)
		dfs(node.Right)
	}
	dfs(root)

	ans := []int{}
	for n, freq := range m {
		if freq == mFreq {
			ans = append(ans, n)
		}
	}

	return ans
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

当然这种方法用了中序遍历和二叉搜索树的特性，保证了遍历的顺序一定是有序的，这样才可以通过判断当前节点的值和前一个节点的值来决定当前数字是否不会再后面的节点中出现。这种方法的时间复杂度是 O(n)，空间复杂度是 O(n)，因为有递归调用栈的开销，但是不需要额外的空间来存储节点的值和出现次数。