LeetCode第501题：二叉搜索树中的众数的Java实现

摘要

LeetCode第501题要求在二叉搜索树（BST）中找出出现次数最多的元素。本文将介绍两种Java实现方法：迭代法和递归法。

1. 问题描述

给定一个二叉搜索树（BST），找出 BST 中出现次数最多的元素。假设任意两个节点的值都是不同的。

2. 示例分析

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

3. 算法设计

3.1 理解二叉搜索树

在二叉搜索树中，所有左子树上的值小于根节点，所有右子树上的值大于根节点。

3.2 迭代法

利用中序遍历的单调性，通过一个变量记录前一个节点的值和出现次数，迭代地遍历BST。

3.3 递归法

通过递归进行中序遍历，同样利用单调性记录节点值和出现次数。

4. Java代码实现

4.1 迭代法

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int[] findMode(TreeNode root) {
        
        int maxCount=0;
        int count=0;
        TreeNode pre=null;
        List<Integer> list=new ArrayList<>();
        Stack<TreeNode> stack=new Stack<>();
        while(root!=null||!stack.isEmpty()){
            while(root!=null){
                stack.push(root);
                root=root.left;
            }
            TreeNode pop=stack.pop();
            if(pre==null||pop.val!=pre.val){
                count=1;
            }else{
                count++;
            }
            int rootValue=pop.val;
            if(count>maxCount){
                list.clear();
                list.add(rootValue);
                maxCount=count;
            }else if(count==maxCount){
                list.add(rootValue);
            }
            pre=pop;
            root=pop.right; 
        }
        return list.stream().mapToInt(Integer::intValue).toArray();

    }
}
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

4.2 递归法

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int maxCount;
    int count;
    TreeNode pre;
    List<Integer> reslist;
    public int[] findMode(TreeNode root) {
        maxCount=0;
        count=0;
        pre=null;
        reslist=new ArrayList<>();
        findMode1(root);
        int[] res=new int[reslist.size()];
        for(int i=0;i<reslist.size();i++){
            res[i]=reslist.get(i);
        }
        return res;

    }
    public void findMode1(TreeNode root){
        if(root==null){
            return;
        };
        findMode1(root.left);
        if(pre==null||pre.val!=root.val){
            count=1;
        }else{
            count++;
        }
        int rootValue=root.val;
        if(count>maxCount){
            reslist.clear();
            reslist.add(rootValue);
            maxCount=count;
        }else if(count==maxCount){
            reslist.add(rootValue);
        }
        pre=root;
        findMode1(root.right);
    }
}

## 5. 代码解析
- **迭代法**：通过模拟中序遍历的过程，使用两个指针`root和`pre`记录当前节点和前一个节点，迭代地更新出现次数最多的值。
- **递归法**：通过递归进行中序遍历，使用一个maxCount每个值的出现次数，最后找出出现次数最多的值。

## 6. 测试验证
使用LeetCode平台或其他测试工具对提供的代码进行测试，确保算法的正确性。

## 7. 总结
LeetCode第501题是一个典型的二叉搜索树问题，通过理解BST的性质和中序遍历的单调性，可以有效地找出出现次数最多的元素。递归法和迭代法都是有效的解决方案。

## 8. 参考文献
- [LeetCode第501题官方题解](https://leetcode.com/problems/find-mode-in-binary-search-tree/solution/)
- [二叉搜索树的中序遍历](https://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion/)

---



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
67
68
69
70
71
72
73
74