
问题
给定一个有相同值的二叉搜索树(BST),找出 BST 中的所有众数(出现频率最高的元素)。
假定 BST 有如下定义:
结点左子树中所含结点的值小于等于当前结点的值
结点右子树中所含结点的值大于等于当前结点的值
左子树和右子树都是二叉搜索树
给定 BST [1,null,2,2],
1
\
2
/
2
返回[2].
提示:如果众数超过1个,不需考虑输出顺序
进阶:你可以不使用额外的空间吗?(假设由递归产生的隐式调用栈的开销不被计算在内)
Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST.
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.
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).
示例
public class Program { public static void Main(string[] args) { var root = new TreeNode(1) { left = new TreeNode(3) { left = new TreeNode(5), right = new TreeNode(7) }, right = new TreeNode(9) }; var res = FindMode(root); ShowArray(res); Console.ReadKey(); } static void ShowArray(int[] array) { foreach(var num in array) { Console.Write($"{num} "); } Console.WriteLine(); } public static int[] FindMode(TreeNode root) { if(root == null) return new int[0]; var dic = new Dictionary<int, int>(); PreOrder(root, ref dic); var max = dic.Values.Max(); return (from r in dic where r.Value == max select r.Key).ToArray(); } public static void PreOrder(TreeNode root, ref Dictionary<int, int> dic) { if(root == null) return; if(dic.ContainsKey(root.val)) { dic[root.val]++; } else { dic[root.val] = 1; } PreOrder(root?.left, ref dic); PreOrder(root?.right, ref dic); } public class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode(int x) { val = x; } } }
以上给出1种算法实现,以下是这个案例的输出结果:
1 3 5 7 9
分析:
显而易见,以上算法的时间复杂度为: 。
本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/4086。