# C#LeetCode刷题之#501-二叉搜索树中的众数​​​​​​​（Find Mode in Binary Search Tree）

1
\
2
/
2

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);

}

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 3 5 7 9`