LeetCode——501 二叉搜尋樹中的衆數(JAVA)

給定一個有相同值的二叉搜尋樹（BST），找出 BST 中的所有衆數（出現頻率最高的元素）。

假定 BST 有如下定義：

• 結點左子樹中所含結點的值小于等于目前結點的值
• 結點右子樹中所含結點的值大于等于目前結點的值
• 左子樹和右子樹都是二叉搜尋樹

例如：

給定 BST

[1,null,2,2]

,

1
    \
     2
    /
   2
           

傳回[2].

提示： 如果衆數超過1個，不需考慮輸出順序

進階： 你可以不使用額外的空間嗎？（假設由遞歸産生的隐式調用棧的開銷不被計算在内）

思路

主要思路就是周遊一遍BST，然後用

HashMap

來記錄每個值出現的次數（值為

key

，出現的次數為

value

），同時記錄最大次數。

然後周遊完BST之後，再周遊

HashMap

，來尋找出現次數最多的數字，如果目前的

map.get(key)==maxValue

的話，就說明找到了一個衆數，加入

ArrayList

中。

最後，再将

ArrayList

裡的答案給數組即可。

代碼

public class Solution {
	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;
		}
	}
	HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
	ArrayList<Integer> list = new ArrayList<Integer>();
	int maxValue = 1;
	public void inOrder(TreeNode root) {
		if(root.left!=null) {
			inOrder(root.left);
		}
		if(map.get(root.val)==null) {//如果是第一次出現
			map.put(root.val, 1);
		}
		else {
			int value = map.get(root.val);
			value++;
			map.put(root.val, value);
			if(value>maxValue) maxValue = value;
		}
		if(root.right!=null) {
			inOrder(root.right);
		}
	}
	public int[] findMode(TreeNode root) {
		inOrder(root);
		for(int key : map.keySet()) {
			if(map.get(key)==maxValue) {
				list.add(key);
			}
		}
		int[] answear = new int[list.size()];
		for(int i=0;i<list.size();i++) {
			answear[i] = list.get(i);
		}
		return answear;
	}
}