LeetCode - Easy - 501. Find Mode in Binary Search Tree

怼烎@ 2022-10-15 15:57 51阅读 0赞

## Topic ##

*  Tree

## Description ##

[https://leetcode.com/problems/find-mode-in-binary-search-tree/][https_leetcode.com_problems_find-mode-in-binary-search-tree]

Given the `root` of a binary search tree (BST) with duplicates, return all the mode(s) (i.e., the most frequently occurred element) in it.

If the tree has more than one mode, return them in **any order**.

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.

**Example 1:**

![2d6ea5d5a756c203cd1ce763cf7b4603.png][]

Input: root = [1,null,2,2]
    Output: [2]

**Example 2:**

Input: root = [0]
    Output: [0]

**Constraints:**

*  The number of nodes in the tree is in the range  \[ 1 , 1 0 4 \] \[1, 10^4\] \[1,104\].
 *   − 1 0 5 < = N o d e . v a l < = 1 0 5 -10^5 <= Node.val <= 10^5 −105<=Node.val<=105

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

## Analysis ##

中序遍历BST类似于按顺序遍历已排序的序列。

## Submission ##

import java.util.ArrayList;
    import java.util.List;
    
    import com.lun.util.BinaryTree.TreeNode;
    
    public class FindModeinBinarySearchTree { 
    	//方法一：需要O(n)空间
        public int[] findMode(TreeNode root) { 
            List<Integer> result = new ArrayList<>(), list = new ArrayList<>();
        	recurse(root, list);
        	
        	int maxCount = 0, startIndex = 0;
        	int lastNum = list.get(startIndex);
        	for(int i = 1; i <= list.size(); i++) { 
        		if(i == list.size() || list.get(i) != lastNum) { 
        			int count = i - startIndex;
        			if(count > maxCount) { 
        				maxCount = count;
        				result.clear();
        				result.add(lastNum);
        			}else if(count == maxCount){ 
        				result.add(lastNum);
        			}
        			startIndex = i;
        			if(i < list.size())
        				lastNum = list.get(i);
        		}
        	}
        	
        	return result.stream()
    				   .mapToInt(Integer::intValue)
    				   .toArray();
        }
        
        private void recurse(TreeNode node, List<Integer> list) { 
        	if(node == null)
        		return;
        	recurse(node.left, list);
        	list.add(node.val);
        	recurse(node.right, list);
        }
        
        
        
        //方法二：无需额外O(n)空间
        public int[] findMode2(TreeNode root) { 
        	List<Integer> result = new ArrayList<>();
        	Integer[] array = { null, 0, 0};//{lastNum, count, maxCount}
        	recurse2(root, array, result);
        	updateCount(array, result);
        	return result.stream()
    				   .mapToInt(Integer::intValue)
    				   .toArray();
        }
        
        private void recurse2(TreeNode node, Integer[] array, List<Integer> result) { 
        	if(node == null)
        		return;
        	recurse2(node.left, array, result);
        	
        	int current = node.val;
        	if(array[0] == null) {  //初始化
        		array[0] = current;
        		array[1] = array[2] = 1;
        	}else { 
        		if(current != array[0]) { 
        			updateCount(array, result);
        			array[0] = current;
        			array[1] = 0;
        		}
        		array[1]++;
        	}
        	
        	recurse2(node.right, array, result);
        }
        
        private void updateCount(Integer[] array, List<Integer> result) { 
    		if(array[1] > array[2]) { 
    			array[2] = array[1];
    			result.clear();
    			result.add(array[0]);
    		}else if(array[1] == array[2]){ 
    			result.add(array[0]);
    		}
        }
        
    }

## Test ##

import static org.junit.Assert.*;
    import static com.lun.util.BinaryTree.*;
    
    import org.junit.Test;
    
    
    public class FindModeinBinarySearchTreeTest { 
    
    	@Test
    	public void test() { 
    		FindModeinBinarySearchTree obj = new FindModeinBinarySearchTree();
    
    		TreeNode root = new TreeNode(1);
    		root.right = new TreeNode(2);
    		root.right.left = new TreeNode(2);
    		
    		
    		assertArrayEquals(new int[] { 2}, obj.findMode(root));
    		assertArrayEquals(new int[] { 0}, obj.findMode(new TreeNode(0)));
    		
    		assertArrayEquals(new int[] { 2}, obj.findMode2(root));
    		assertArrayEquals(new int[] { 0}, obj.findMode2(new TreeNode(0)));
    		
    	}	
    }

[https_leetcode.com_problems_find-mode-in-binary-search-tree]: https://leetcode.com/problems/find-mode-in-binary-search-tree/
[2d6ea5d5a756c203cd1ce763cf7b4603.png]: /images/20221014/2408c85355fc485fa13afc6c8e27d3d2.png