[LeetCode] 501. Find Mode in Binary Search Tree

轉自LeetCode

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.

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

<Solution>

想法如下

• 用任何 binary tree traversal 的方式歷遍一次，算出最多的出現次數，同時也用 hashmap 記錄每個數字出現的次數。這邊因為想要讓空間複雜度為 O(1)，所以使用 Morris Traversal (inorder)

• 找出最多次數後，把 hashmap 裡面出現次數等於最多次數的數字，放到答案裡就可以了

code 如下

C++

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	vector<int> findMode(TreeNode* root) {
	unordered_map<int, int> hashmap;
	int maxFreq = INT_MIN;
	int cnt;
	TreeNode *cur = root, *prev = NULL;
	while(cur) {
	if(!cur->left) {
	cnt = hashmap[cur->val] + 1;
	hashmap[cur->val] = cnt;
	maxFreq = max(maxFreq, cnt);
	cur = cur->right;
	}
	else {
	prev = cur->left;
	while(prev->right && prev->right != cur) {
	prev = prev->right;
	}
	if(!prev->right) {
	prev->right = cur;
	cur = cur->left;
	}
	else {
	cnt = hashmap[cur->val] + 1;
	hashmap[cur->val] = cnt;
	maxFreq = max(maxFreq, cnt);
	prev->right = NULL;
	cur = cur->right;
	}
	}
	}
	vector<int> ans;
	for(const auto &it : hashmap) {
	if(it.second == maxFreq) {
	ans.push_back(it.first);
	}
	}
	return ans;
	}
	};

view raw findModeInBinarySearchTree.cpp hosted with ❤ by GitHub

Java

	/**
	* Definition for a binary tree node.
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	class Solution {
	public int[] findMode(TreeNode root) {
	HashMap<Integer, Integer> map = new HashMap<>();
	TreeNode cur = root, prev = null;
	int maxFreq = Integer.MIN_VALUE;
	int cnt;
	while(cur != null) {
	if(cur.left == null) {
	map.put(cur.val, map.getOrDefault(cur.val, 0) + 1);
	maxFreq = Math.max(maxFreq, map.get(cur.val));
	cur = cur.right;
	}
	else {
	prev = cur.left;
	while(prev.right != null && prev.right != cur) {
	prev = prev.right;
	}
	if(prev.right == null) {
	prev.right = cur;
	cur = cur.left;
	}
	else {
	map.put(cur.val, map.getOrDefault(cur.val, 0) + 1);
	maxFreq = Math.max(maxFreq, map.get(cur.val));
	prev.right = null;
	cur = cur.right;
	}
	}
	}
	ArrayList<Integer> ans = new ArrayList<>();
	for(final int k : map.keySet()) {
	if(map.get(k) == maxFreq) {
	ans.add(k);
	}
	}
	//>> java8
	return ans.stream().mapToInt(Integer::intValue).toArray();
	}
	}

view raw findModeInBinarySearchTree.java hosted with ❤ by GitHub

kotlin

	/**
	* Example:
	* var ti = TreeNode(5)
	* var v = ti.`val`
	* Definition for a binary tree node.
	* class TreeNode(var `val`: Int) {
	* var left: TreeNode? = null
	* var right: TreeNode? = null
	* }
	*/
	class Solution {
	fun findMode(root: TreeNode?): IntArray {
	val stack = mutableListOf<TreeNode>()
	val map = mutableMapOf<Int,Int>()
	var max = Int.MIN_VALUE
	var cur = root
	while(cur != null || stack.isNotEmpty()) {
	while(cur != null) {
	stack.add(cur!!)
	cur = cur?.left
	}
	cur = stack.last()
	stack.removeAt(stack.lastIndex)
	map[cur!!.`val`] = map[cur!!.`val`]?.let{it+1} ?: 1
	max = Math.max(max, map[cur!!.`val`]!!)
	cur = cur?.right
	}
	val ans = mutableListOf<Int>()
	for(m in map) {
	if(m.value == max) {
	ans.add(m.key)
	}
	}
	return ans.toIntArray()
	}
	}

view raw find_mode_in_binary_search_tree.kt hosted with ❤ by GitHub