题目：

Given a binary search tree (BST) with duplicates, find all the (the most frequently occurred element) in the given BST.

给定具有重复项的二叉搜索树（BST），找到给定BST中的所有众数（最频繁出现的元素）。

Assume a BST is defined as follows:

假设BST定义如下：

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.左右子树也必须是二叉搜索树。

For example:

Given BST [1,null,2,2],

1    \     2    /   2

return [2].

Note: If a tree has more than one mode, you can return them in any order.

注意：如果树有多个模式，您可以按任何顺序返回它们。

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

跟进：你可以不使用任何额外的空间吗？（假设由于递归而产生的隐式堆栈空间不计算）。

解答：

方法一：时间复杂度：O（n），空间复杂度：O（n）

1 /** 2  * Definition for a binary tree node. 3  * public class TreeNode { 4  *     int val; 5  *     TreeNode left; 6  *     TreeNode right; 7  *     TreeNode(int x) { val = x; } 8  * } 9  */10 class Solution {11     Map
     
       map=new HashMap<>();12     int maxTimes;13     public int[] findMode(TreeNode root) {14         if(root==null) return new int[0];15         inorder(root);16         17         List
      
        list=new ArrayList<>();18         for(int key:map.keySet()){19             if(map.get(key)==maxTimes)20                 list.add(key);21         }22         23         int[] res=new int[list.size()];24         for(int i = 0; i

方法二：

1 /** 2  * Definition for a binary tree node. 3  * public class TreeNode { 4  *     int val; 5  *     TreeNode left; 6  *     TreeNode right; 7  *     TreeNode(int x) { val = x; } 8  * } 9  */10 class Solution {11     Integer prev=null;12     int maxTimes=0;13     int count=1;14     15     public int[] findMode(TreeNode root) {16         if(root==null) return new int[0];17         18         List
     
       list=new ArrayList<>();19         inorder(root,list);20         21         int[] res=new int[list.size()];22         for(int i=0;i
      
        list){28         if(node==null) return;29         inorder(node.left,list);30         if(prev!=null){31             if(node.val==prev)32                 count++;33             else34                 count=1;35         }36         if(count>maxTimes){37             list.clear();38             list.add(node.val);39             maxTimes=count;40         }else if(count==maxTimes){41             list.add(node.val);42         }43         prev=node.val;44         inorder(node.right,list);45     }46 }

详解：

方法一：

哈希表：记录数字和其出现次数之前的映射，变量maxTimes：记录当前最多的次数值（适用于任何寻找众数的树，任意一种遍历方式均可，这里选择中序遍历）

方法二：

题目跟进，不需要额外存储空间，则无法使用哈希表。利用二分搜索树的性质，本身即有序，相同的元素连在一起

prev：相同元素的第一个节点

maxTimes：最大次数

count：当前元素出现次数

转载于:https://www.cnblogs.com/chanaichao/p/9579293.html

你可能感兴趣的文章