未完待续。。。
1.leetcode 671
1.1题目描述
leetcode_671
1.2代码
/*
注意:
1)最小值一定是根节点
2)求出左右子树中的最小值就是第二小的值,
且这个值不能等于 root.val(最小值),并且注意样例 [2,2,2]
3)添加 flag 标志位,确保 min 被修改(存在比最小值小的数)已知。
*/
public int findSecondMinimumValue(TreeNode root) {
int min = Integer.MAX_VALUE;
int flag = 0;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()){
TreeNode pop = stack.pop();
if(pop.val != root.val){
if(pop.val<=min){
min = pop.val;
flag = 1;
}
}
if(pop.right!=null) stack.push(pop.right);
if(pop.left!=null) stack.push(pop.left);
}
if(min == root.val || flag==0) return -1;
return min;
}
public int findSecondMinimumValue2(TreeNode root) {
int first = Integer.MAX_VALUE;
int second = Integer.MAX_VALUE;
//count 值被修改过了,表示存在第二小的值
int count = 0;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode pop = stack.pop();
if(pop.val<first){
second = first;
first = root.val;
}
//注意: pop.val 要 = second 否则样例: [2,2,2147483647] 过不了
else if(pop.val>first && pop.val<=second){
second = pop.val;
count++;
}
if (pop.right != null) stack.push(pop.right);
if (pop.left != null) stack.push(pop.left);
}
return count==0?-1:second;
}
网友评论