LeetCode Find Mode in Binary Search Tree
原题链接在这里:https://leetcode.com/problems/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).
题解:
两遍Binary Tree Inorder Traversal.
第一遍找出有几个mode. 建立res array, 并保留了mode duplicate次数是多少. 第二遍当duplicate次数是mode 的duplicate次数时就加入res中.
Time Complexity: O(n).
Space: O(n), 每个节点都不同, res的size就是O(n). stack space O(logn). 如果利用Binary Tree Inorder Traversal中的Morris Traversal方法可以不用stack space.
AC Java:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
int curVal;
int curCount;
int maxCount;
int modeNumber;
int [] res; public int[] findMode(TreeNode root) {
inorderTraversal(root);
res = new int[modeNumber];
curCount = 0;
modeNumber = 0;
inorderTraversal(root);
return res;
} private void inorderTraversal(TreeNode root){
if(root == null){
return;
} inorderTraversal(root.left);
handleCurrentNodeValue(root.val);
inorderTraversal(root.right);
} private void handleCurrentNodeValue(int val){
if(val != curVal){
curVal = val;
curCount = 0;
}
curCount++; if(curCount > maxCount){
maxCount = curCount;
modeNumber = 1;
}else if(curCount == maxCount){
if(res != null){
res[modeNumber] = curVal;
}
modeNumber++;
}
}
}
最新文章
- 在进行javaIO写文件操作后文件内容为空的情况
- CodeForces - 404B(模拟题)
- mysql实用指南
- UVA 534 - Frogger(kruskal扩展)
- multipleOutputs Hadoop
- centos中NAT模式下静态IP连接外网
- 数据库及SQL----常用知识点总结
- MySql在生产环境中是用mysqldump还是xtrabackup备份和恢复数据
- mac 下利用AndroidStudio APK获取签名信息
- SA-题目
- MySQL(二)数据的检索和过滤
- PopupWindow下拉列表
- 解决 dpkg: warning: files list file for package 'x' missing 问题
- Myelipse中xml约束文件的导入(以spring为例)
- angularjs学习第三天笔记(过滤器第二篇---filter过滤器及其自定义过滤器)
- htnl类名命规范
- ASCII 、UTF-8、Unicode都是个啥啊,为啥会乱码啊?
- 1.4 C++内联函数(inline)
- 你以为在用SharePoint但其实不是
- std::thread函数传参拷贝次数