LeetCode（Binary Search Tree)501. Find Mode in Binary Search Tree

绝地灬酷狼 2023-09-26 20:39 15阅读 0赞

# 1.问题 #

Given the root of a binary search tree (BST) with duplicates, return all the mode(s) (i.e., the most frequently occurred element) in it.

If the tree has more than one mode, return them in any order.

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than or equal to the node’s key.  
The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.  
Both the left and right subtrees must also be binary search trees.

Example 1:  
![在这里插入图片描述][e2083f30c6c847049a0bca5366ada761.png]

> Input: root = \[1,null,2,2\]  
> Output: \[2\]

Example 2:

> Input: root = \[0\]  
> Output: \[0\]

Constraints:

*  The number of nodes in the tree is in the range \[1, 104\].
 *  \-105 <= Node.val <= 105

`Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).`

# 2. 解题思路 #

## 方法1： ##

> 1.定义一个哈希表用于存储每个节点的值和出现次数，以及一个变量记录出现次数最多的节点出现次数。  
> 2.对二叉树进行中序遍历，对于每个节点，将其节点值在哈希表中对应的出现次数加1，并更新最大出现次数。  
> 3.遍历哈希表，将出现次数等于最大出现次数的节点值添加到一个列表中。  
> 4.将列表转换成数组形式作为结果返回。

## 方法2： ##

> 1.  基于中序遍历实现的。
> 2.  在遍历过程中，维护三个变量：prev、count和maxCount。
> 3.  prev表示上一个遍历的节点的值。
> 4.  count表示当前节点的值在当前遍历路径上的出现次数。
> 5.  maxCount表示当前路径上任何一个节点的出现次数的最大值。
> 6.  在遍历到当前节点时，如果当前节点值等于上一个节点值，则将count加1，否则将count重置为1。
> 7.  然后，如果count的值大于maxCount，则将maxCount更新为count，并且将result清空，将当前节点值添加到result中；如果count等于maxCount，则将当前节点值添加到result中。
> 8.  最后，将result转换成数组返回即可。

# 3. 代码 #

## 代码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 {
        
        Map<Integer, Integer> map = new HashMap<>(); // 哈希表用于存储节点值和出现次数
        int maxCount = 0; // 记录出现次数最多的节点出现次数
        
        public int[] findMode(TreeNode root) {
        
            inOrder(root); // 中序遍历二叉树，统计每个节点出现次数
            List<Integer> list = new ArrayList<>();
            for (int key : map.keySet()) {
         // 遍历哈希表
                if (map.get(key) == maxCount) {
         // 如果该节点出现次数等于最大出现次数
                    list.add(key); // 添加到列表中
                }
            }
            int[] res = new int[list.size()]; // 创建结果数组
            for (int i = 0; i < res.length; i++) {
         // 遍历列表，将结果转换成数组形式
                res[i] = list.get(i);
            }
            return res;
        }
        
        private void inOrder(TreeNode node) {
         // 中序遍历二叉树，统计每个节点出现次数
            if (node == null) {
        
                return;
            }
            inOrder(node.left);
            int count = map.getOrDefault(node.val, 0) + 1; // 获取节点值在哈希表中的出现次数并加1
            map.put(node.val, count); // 更新哈希表中节点值的出现次数
            maxCount = Math.max(maxCount, count); // 更新最大出现次数
            inOrder(node.right);
        }
    }

## 代码2： ##

class Solution {
        
        private int prev = -1;
        private int count = 1;
        private int maxCount = 0;
        private List<Integer> result = new ArrayList<>();
    
        public int[] findMode(TreeNode root) {
        
            inorder(root);
            int[] res = new int[result.size()];
            for (int i = 0; i < result.size(); i++) {
        
                res[i] = result.get(i);
            }
            return res;
        }
    
        private void inorder(TreeNode root) {
        
            if (root == null) {
        
                return;
            }
            inorder(root.left);
            if (prev != -1) {
        
                if (root.val == prev) {
        
                    count++;
                } else {
        
                    count = 1;
                }
            }
            if (count > maxCount) {
        
                maxCount = count;
                result.clear();
                result.add(root.val);
            } else if (count == maxCount) {
        
                result.add(root.val);
            }
            prev = root.val;
            inorder(root.right);
        }
    }

> 和代码2的思路基本相同  
> `相同`：使用中序遍历二叉搜索树，统计每个数字出现的次数，根据出现次数更新结果集和最大出现次数。  
> `不同`：使用了 List 来存储结果集，而之前的代码使用了 int\[\]，另外，这段代码在遍历每个数字时，使用 pre 变量记录当前数字的前一个数字，而之前的代码则是在递归中传入参数。

class Solution {
        
        // 定义结果集
        List<Integer> list = new ArrayList<>();
        // 当前数字出现的次数和出现次数最多的数字的出现次数
        int curCount = 0, maxCount = 0;
        // 用于记录当前数字的前一个数字
        Integer pre = null;
    
        public int[] findMode(TreeNode root) {
        
            // 中序遍历
            inorder(root);
            int[] res = new int[list.size()];
            for (int i = 0; i < list.size(); i++) {
        
                res[i] = list.get(i);
            }
            return res;
        }
    
        private void inorder(TreeNode root) {
        
            if (root == null) {
        
                return;
            }
            // 遍历左子树
            inorder(root.left);
            // 统计当前数字出现的次数
            if (pre != null && pre == root.val) {
        
                curCount++;
            } else {
        
                curCount = 1;
            }
            // 根据出现次数更新结果集和maxCount
            if (curCount == maxCount) {
        
                list.add(root.val);
            } else if (curCount > maxCount) {
        
                list.clear();
                list.add(root.val);
                maxCount = curCount;
            }
            // 更新pre
            pre = root.val;
            // 遍历右子树
            inorder(root.right);
        }
    }

[e2083f30c6c847049a0bca5366ada761.png]: https://img-blog.csdnimg.cn/e2083f30c6c847049a0bca5366ada761.png