501-Find Mode in Binary Search Tree

Description

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

---

问题描述

给定一个有重复值的二叉排序树， 找出其所有的模式(最频繁的值)

假设二叉排序树如下定义:

左子树只包含小于等于节点值的节点右子树只包含大于等于节点值的节点左右子树也为二叉排序树

---

问题分析

进行两次中序遍历， 第一次获取模式个数(用来创建数组)以及次数， 第二次往数组里面存值

---

解法

public class Solution { private int currVal; //当前值的个数 private int currCount = 0; //当前最大个数 private int maxCount = 0; //模式个数 private int modeCount = 0; private int[] modes; public int[] findMode(TreeNode root) { inorder(root); //注意这里 modes = new int[modeCount]; //注意， 没有重置maxCount modeCount = 0; currCount = 0; inorder(root); return modes; } private void handleValue(int val){ if(val != currVal){ currVal = val; currCount = 0; } currCount++; if(currCount > maxCount){ maxCount = currCount; modeCount = 1; }else if(currCount == maxCount){ if(modes != null) modes[modeCount] = currVal; modeCount++; } } private void inorder(TreeNode root){ if (root == null) return; inorder(root.left); handleValue(root.val); inorder(root.right); } }