FindModeInBinarySearchTreeOPT2 [source code]
public class FindModeInBinarySearchTreeOPT2 {
static
/******************************************************************************/
public class Solution {
int curVal;
int maxcount = 0;
int count = 0;
int modecount = 0;
int[] modes;
public int[] findMode(TreeNode root) {
inOrder(root);
modes = new int[modecount];
modecount = 0;
count = 0;
inOrder(root);
return modes;
}
public void handleValue(int val) {
if (curVal != val) {
curVal = val;
count = 1;
} else {
count++;
}
if (count > maxcount) {
maxcount = count;
modecount = 1;
} else if (count == maxcount) {
if (modes != null) modes[modecount] = curVal;
modecount++;
}
}
public void inOrder(TreeNode root) {
if (root == null) return;
inOrder(root.left);
handleValue(root.val);
inOrder(root.right);
}
}
/******************************************************************************/
public static void main(String[] args) {
FindModeInBinarySearchTreeOPT2.Solution tester = new FindModeInBinarySearchTreeOPT2.Solution();
}
}
这个是另外一个 submission 最优解: 7(74);
这个解法其实挺直白的, 就是理解了一个关键点: BST 对于这个问题的穷搜方法的贡献, 就是 BST 你可以就看成是一个sorted array, 前提是你 DFS iterate 的时候走的是 In Order 的路线, 那么最后就跟 input 给你的是一个sorted array是没有区别的;
这个人的代码的空间优化就是建立在这个前提的基础上的, 因为如果这个是一个 sorted 的, 那么你只要几个 buffer 就可以在走的时候保存各种信息了;
这个人的算法最后实际上是走了两个pass, 这个是因为这个题目规定不能有extra space, 所以我们不能用 list, 就只能先单独走一个 pass 来找到最后 res 的 array 的长度先. 然后第二个 pass 再来填满这个 array.
代码上面, 只要在某一个部分加一个 filter 来判断 modes 是否已经被 init 就行了;
总体来说这个算法赢在理解了 BST 的一个关键点;
另外我们以前经常说 tree 的问题, 可以从 recursion 和 iteration(DFS) 两个思路去考虑.
这一题, 其实从 recursion 的角度是没有什么突破口的, 因为如果你思考 recursion, 也就是考虑两个 child 的既有结果怎样对 root 的结果做出贡献, 你最终是要想办法找到一个recursive return value, which satisfies DP property的. 这里是找不到这样一个返回值的;
这个题目的考点其实很简单, 就是把一个普通的 count 题放到一个 tree 的环境下面来考你; 所以关键点是理解在 tree 问题上面的 iteration 是怎么完成的: DFS, 以及怎么理解 DFS. 比如这一题, In Order 这一个点, 你要捕捉到. 我自己的暴力搜, 是不用在乎是否是 In Order 的, 但是他这个做法, 就必须用 In Order(保证 iterate 是按照一个sorted/ascending(nondescending))的顺序去走;
--
看了 discussion 好像这个代码的作者是 Stefan, 这个是他对于O(1) space 的解释:
I've seen several solutions claimed to be O(1) space, but I disagree. They traverse the tree in in-order and keep track of the current set of modes (among other things). But that's not O(1) space, not even when disregarding recursion stack space (as explicitly allowed) and result space (not mentioned but reasonable). The set's contents aren't on stack space, so it can't be disregarded that way. And if the values are for example 1,2,3,4,...,n-2,n-1,n-1 (unique values followed by one double value), the set grows to Ω(n) and it can't be disregarded because the result only has size 1.
I think the way to do it properly is to do two passes. One to find the highest number of occurrences of any value, and then a second pass to collect all values occurring that often. Any other ideas?
Here's a (two-pass) solution that I think can rightfully be called O(1) space. Both passes keep track of the current value etc, and the second pass additionally collects the modes in the result array. I took the value handling out of the in-order traversal into its own function for clarity. Also, this way you could very easily replace my recursive in-order traversal with for example Morris traversal. Then you wouldn't even need to disregard the recursion stack space in order to claim O(1) extra space usage.
public class Solution {
public int[] findMode(TreeNode root) {
inorder(root);
modes = new int[modeCount];
modeCount = 0;
currCount = 0;
inorder(root);
return modes;
}
private int currVal;
private int currCount = 0;
private int maxCount = 0;
private int modeCount = 0;
private int[] 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);
}
}
Edit: Here's Morris traversal, just replace my previous inorder function with this. I hadn't realized it earlier, but having my separate handleValue function doesn't just nicely separate the traversal logic from this problem's logic, but it's also beneficial for Morris traversal because I'm calling handleValue from two different places in the code!
private void inorder(TreeNode root) {
TreeNode node = root;
while (node != null) {
if (node.left == null) {
handleValue(node.val);
node = node.right;
} else {
TreeNode prev = node.left;
while (prev.right != null && prev.right != node)
prev = prev.right;
if (prev.right == null) {
prev.right = node;
node = node.left;
} else {
prev.right = null;
handleValue(node.val);
node = node.right;
}
}
}
}
这个算法总体上是有点复杂的, 在 bear 上面有专门的记在;
不过这个算法唯一的优势, 就是连 recursion Stack 都不需要, 就可以完成一个 DFS 的 traversal;
可以看到这个 Morris 跟这个问题的融合还是很直接的, 因为 Morris 说到底就是一个 traversal 的 iteration 的顺序而已, 至于真正针对每一个被 iterate 到的 node 怎么操作, 直接写进去就行了;
Problem 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).
Difficulty:Easy
Category:Algorithms
Acceptance:37.96%
Contributor: Coder_1215
Companies
google
Related Topics
tree
Similar Questions
Validate Binary Search Tree