503，二叉搜索树中的众数

Original 山大王wld 数据结构和算法 2022-05-09

收录于合集 #算法图文分析 161个

What drains your spirit drains your body. What fuels your spirit fuels your body.

消耗你心灵的事物也会消耗你的健康，滋补你心灵的事物也会滋补你的身体。

问题描述

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

假定 BST 有如下定义：

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

例如：

给定 BST [1,null,2,2],

1 \ 2 / 2

返回[2].

提示：如果众数超过1个，不需考虑输出顺序

二叉树的中序遍历解决

这题是让求二叉搜索树中的众数，也就是出现次数最多的那个数。如果是在一个排序的数组中找众数，这个可能就比较简单，但这题是让在二叉搜索树中查找。

我们都知道二叉搜索树的中序遍历是有序的，有一种方式就是先把二叉搜索树中序遍历的结果存放到一个数组中，因为这个数组是升序的（虽然有重复的），我们可以遍历这个数组，这里使用几个变量。

使用变量curent表示当前的值，count表示当前值的数量，maxCount表示重复数字最大的数量。list集合存放结果。

1，如果当前节点的值等于curent，count就加1，

2，如果当前节点的值不等于current，说明遇到了下一个新的值，更新current为新的值，然后让count=1；

接着比较count和maxCount的大小，

如果count==maxCount，就把当前节点的值加入到集合list中。
如果count>maxCount，说明遇到重复次数最高的数了，这里先把list集合清空，然后再把当前节点的值加入到集合list中，最后在更新maxCount的值。

如果先把树的节点找出来在计算有点麻烦，我们可以在遍历树的节点的时候就判断，这样就会好一些，下面使用两种方式，一种是递归的，一种是非递归的。树的中序遍历顺序如下

左子节点→当前节点→右子节点

二叉树的中序遍历代码

1public void inOrderTraversal(TreeNode node) {
2    if (node == null)
3        return;
4    inOrderTraversal(node.left);
5    System.out.println(node.val);
6    inOrderTraversal(node.right);
7}

我们来对他进行改造一下

 1List<Integer> mList = new ArrayList<>();
 2int curent = 0;//表示当前节点的值
 3int count = 0;//和当前节点值相同的节点数量
 4int maxCount = 0;//最大的重复数量
 5
 6public int[] findMode(TreeNode root) {
 7    inOrderTraversal(root);
 8    int[] res = new int[mList.size()];
 9    //把集合list转化为数组
10    for (int i = 0; i < mList.size(); i++) {
11        res[i] = mList.get(i);
12    }
13    return res;
14}
15
16//递归方式
17public void inOrderTraversal(TreeNode node) {
18    //终止条件判断
19    if (node == null)
20        return;
21    //遍历左子树
22    inOrderTraversal(node.left);
23
24    //下面是对当前节点的一些逻辑操作
25    int nodeValue = node.val;
26    if (nodeValue == curent) {
27        //如果节点值等于curent，count就加1
28        count++;
29    } else {
30        //否则，就表示遇到了一个新的值，curent和count都要
31        //重新赋值
32        curent = nodeValue;
33        count = 1;
34    }
35    if (count == maxCount) {
36        //如果count == maxCount，就把当前节点加入到集合中
37        mList.add(nodeValue);
38    } else if (count > maxCount) {
39        //否则，当前节点的值重复量是最多的，直接把list清空，然后
40        //把当前节点的值加入到集合中
41        mList.clear();
42        mList.add(nodeValue);
43        maxCount = count;
44    }
45
46    //遍历右子树
47    inOrderTraversal(node.right);
48}

之前在讲到373，数据结构-6,树的时候，提到二叉树中序遍历的非递归写法

 1public void inOrderTraversal(TreeNode tree) {
 2    Stack<TreeNode> stack = new Stack<>();
 3    while (tree != null || !stack.isEmpty()) {
 4        while (tree != null) {
 5            stack.push(tree);
 6            tree = tree.left;
 7        }
 8        if (!stack.isEmpty()) {
 9            tree = stack.pop();
10            System.out.println(tree.val);
11            tree = tree.right;
12        }
13    }
14}

再来改造一下

 1List<Integer> mList = new ArrayList<>();
 2int curent = 0;
 3int count = 0;
 4int maxCount = 0;
 5
 6public int[] findMode(TreeNode root) {
 7    inOrderTraversal(root);
 8    int[] res = new int[mList.size()];
 9    //把集合list转化为数组
10    for (int i = 0; i < mList.size(); i++) {
11        res[i] = mList.get(i);
12    }
13    return res;
14}
15
16//非递归方式
17public void inOrderTraversal(TreeNode tree) {
18    Stack<TreeNode> stack = new Stack<>();
19    while (tree != null || !stack.isEmpty()) {
20        while (tree != null) {
21            stack.push(tree);
22            tree = tree.left;
23        }
24        if (!stack.isEmpty()) {
25            tree = stack.pop();
26            int nodeValue = tree.val;
27            if (nodeValue == curent) {
28                //如果节点值等于curent，count就加1
29                count++;
30            } else {
31                //否则，就表示遇到了一个新的值，curent和count都要
32                //重新赋值
33                curent = nodeValue;
34                count = 1;
35            }
36            if (count == maxCount) {
37                //如果count == maxCount，就把当前节点加入到集合中
38                mList.add(nodeValue);
39            } else if (count > maxCount) {
40                //否则，当前节点的值重复量是最多的，直接把list清空，然后
41                //把当前节点的值加入到集合中
42                mList.clear();
43                mList.add(nodeValue);
44                maxCount = count;
45            }
46            tree = tree.right;
47        }
48    }
49}