SecondMinimumNodeInABinaryTree [source code]
public class SecondMinimumNodeInABinaryTree {
static
/******************************************************************************/
class Solution {
int first_min = Integer.MAX_VALUE;
int second_min = Integer.MAX_VALUE;
public int findSecondMinimumValue(TreeNode root) {
dfs (root);
return second_min == Integer.MAX_VALUE ? -1 : second_min;
}
void dfs (TreeNode root) {
if (root == null)
return;
if (root.val < first_min) {
second_min = first_min;
first_min = root.val;
} else if (root.val != first_min && root.val < second_min) {
second_min = root.val;
}
dfs (root.left);
dfs (root.right);
}
}
/******************************************************************************/
public static void main(String[] args) {
SecondMinimumNodeInABinaryTree.Solution tester = new SecondMinimumNodeInABinaryTree.Solution();
}
}
笨办法就很简单, 直接走一遍, 然后维护两个min就行了; 不过感觉这个方法其实没有怎么利用到这个tree本身的特性;
想了一个很简单的方法, 这个second是不是永远可以在头两个level找到? 不一定, 可能会一直向下藏; 这个观察也是用人逻辑分析之后找到的;
不过我想到一个问题, 就算你真的是找到了一个单纯利用recursion的算法, 其实本质上也是一个遍历, walk tree的做法啊, 只不过写起来更加好看而已;
ver1的逻辑, 就是在一个level, 判断两个child是否相等, 如果不相等, 就简单, 直接返回larger, 但是如果相等, 就要向下递归两个值上来, 然后比较是否是invalid ret, 进行处理; 但是这个逻辑被这个test: [1,1,3,1,1,3,4,3,1,1,1,3,8,4,8,3,3,1,6,2,1] 给break掉了; 问题好像是因为对于level children不相等的处理太简单了;
想了想还是想直接用笨办法来写算了, 主要是很长时间也没有刷题了, 本身也有点手生了, 想要搞什么neat的方法也搞不定了;
最后搞定的就是上面这个方法, 很简单的笨办法. 注意, 即使是这个笨办法, 其实也不是完全的trivial, 这里有一个multiple peak的维护问题, 就是你注意我在维护部分的代码的第二个branch, 当对min1进行维护失败之后, 对于min2进行判断的时候, 要保证之前这个失败的原因不是因为==min1, 不然可能会出现一个维护多个duplicate的问题;
后来我想了一下, 这个问题其实有一个更简单的方法, 因为这里要维护的peak很少, 所以直接就用一个set也可以啊! 这样就避免了这个duplicate的问题; 这个也不是一个很trivial的优化, 想法, 我认为可以说是一个multiple peak问题的recommended的思路;
最后的速度是3ms (33%), 一般化吧, 这种笨办法, 本身也就是这个速度了;
这个是标准答案: https://leetcode.com/articles/second-minimum-node-in-a-binary-tree/
第一种做法:
class Solution {
public void dfs(TreeNode root, Set<Integer> uniques) {
if (root != null) {
uniques.add(root.val);
dfs(root.left, uniques);
dfs(root.right, uniques);
}
}
public int findSecondMinimumValue(TreeNode root) {
Set<Integer> uniques = new HashSet<Integer>();
dfs(root, uniques);
int min1 = root.val;
long ans = Long.MAX_VALUE;
for (int v : uniques) {
if (min1 < v && v < ans) ans = v;
}
return ans < Long.MAX_VALUE ? (int) ans : -1;
}
}
这个就是正好是我前面的说过的做法; 不过我本身的做法还想要多一个要素, 就是同时维护这个set的size不超过2; 但是这个其实也不是必要的, 因为并不能导致最后时间复杂度降低;
approach2:
class Solution {
int min1;
long ans = Long.MAX_VALUE;
public void dfs(TreeNode root) {
if (root != null) {
if (min1 < root.val && root.val < ans) {
ans = root.val;
} else if (min1 == root.val) {
dfs(root.left);
dfs(root.right);
}
}
}
public int findSecondMinimumValue(TreeNode root) {
min1 = root.val;
dfs(root);
return ans < Long.MAX_VALUE ? (int) ans : -1;
}
}
这个就是我上面交的做法, 其实还是一样的, 都是穷搜;
submission里面有一些其他的奇怪办法:
class Solution {
public int findSecondMinimumValue(TreeNode root) {
if(root == null){
return -1;
}
if(root.left == null && root.right == null){
return -1;
}
int left = root.left.val;
int right = root.right.val;
if(root.left.val == root.val){
left = findSecondMinimumValue(root.left);
}
if(root.right.val == root.val){
right = findSecondMinimumValue(root.right);
}
if(left != -1 && right != -1){
return Math.min(left, right);
}
if(left != -1){
return left;
}
if(right != -1){
return right;
}
return right;
}
}
不过最后速度其实是一样的;
在尝试理解这个算法的时候, 我提炼了一下之前break我的算法的case的核心: [1,1,3,1,2]; 这样一个tree的问题是, 你不能简单的在一个level的两个children里面只重视smaller的那一个, 就像我之前的做法一样, 正确的做法就应该是, 虽然larger的那个一个很可能不是你最后需要参与比较的那一个, 但是你还是要把这个值纳入到考虑当中.
这个是discussion里面一个简化版的写法:
public int findSecondMinimumValue(TreeNode root) {
if(root.left == null) return -1;
int l = root.left.val == root.val ? findSecondMinimumValue(root.left) : root.left.val;
int r = root.right.val == root.val ? findSecondMinimumValue(root.right) : root.right.val;
return l == -1 || r == -1 ? Math.max(l, r) : Math.min(l, r);
}
其实是一样的, 非要写的这么少而已; 核心技巧, 还是要考虑到初始值的设置: 初始值是child自己, 然后conditionally update to the result of downward recursion;
这个是discussion里面另外一个高票的解法:
@zestypanda said in C++, DFS recursion:
This question is very similar to searching for minimum value in the Binary Tree.
The only requirement is that this value must be different from the root value, k.If the root value of a subtree == k, keep searching its children. else, return the root value because it is the minimum of current subtree.
class Solution {
public:
int findSecondMinimumValue(TreeNode* root) {
if (!root) return -1;
int ans = minval(root, root->val);
return ans;
}
private:
int minval(TreeNode* p, int first) {
if (p == nullptr) return -1;
if (p->val != first) return p->val;
int left = minval(p->left, first), right = minval(p->right, first);
// if all nodes of a subtree = root->val,
// there is no second minimum value, return -1
if (left == -1) return right;
if (right == -1) return left;
return min(left, right);
}
};
这个解法相对普通的搜索还是稍微non trivial了一点, 但是我感觉本质上其实还是穷搜, 还是没有利用到题目给的tree property;
这个题目总体最后还是没有找到一个能够合理利用tree Property的解法, 这个可能也是为什么最后这个题目被downvote了很多; 暂时就先这样了;
另外一个教训就是, 还是不要overthink LeetCode的题目; 很多题目真的没有那么复杂的; 包括这个题目, 其实一个很简单的做法就可以做完了, 但是给了很多线索, 让你看起来好像觉得这个问题肯定有什么玄机一样, 结果到现在都一个学期过去了, 根本没有人找到这个什么玄机; 所以你自己真正面试做题目, 还是先从笨办法开始做起来; 然后一点一点开始优化; 比如这里, 转换成用set这种优化, 其实就是在笨办法上面的一个很简单的优化而已;
当然有时候你可能会想要跳出box, 找到一个全新的思路, 但是有一个caveat: 你可以尝试这样, 尤其是跟这题这样, 看起来很故弄玄虚的题目; 但是如果常事了一会儿还是没有头绪, 就要赶紧先搁下来, 然后回头从笨办法慢优化开始重新来过; done is better than perfect.
Problem Description
Given a non-empty special binary tree consisting of nodes with the non-negative value, where each node in this tree has exactly two or zero sub-node. If the node has two sub-nodes, then this node's value is the smaller value among its two sub-nodes.
Given such a binary tree, you need to output the second minimum value in the set made of all the nodes' value in the whole tree.
If no such second minimum value exists, output -1 instead.
Example 1:
Input:
2
/ \
2 5
/ \
5 7
Output: 5
Explanation: The smallest value is 2, the second smallest value is 5.
Example 2:
Input:
2
/ \
2 2
Output: -1
Explanation: The smallest value is 2, but there isn't any second smallest value.
Difficulty:Easy
Total Accepted:2.8K
Total Submissions:6.7K
Contributor: CDY_Saikou
Companies
linkedin
Related Topics
tree
Similar Questions
Kth Smallest Element in a BST