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.
不是二叉搜索树!当心,必须要过完所有的结点才知道答案!
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def findSecondMinimumValue(self, root):
"""
:type root: TreeNode
:rtype: int
"""
inf = float('inf')
min1, min2 = inf, inf
# min1 < min2
def dfs(node):
nonlocal min1, min2
if not node: return
dfs(node.left)
if node.val != min1 and node.val != min2:
if node.val < min1:
min2 = min1
min1 = node.val
elif node.val < min2:
min2 = node.val
dfs(node.right)
assert root
dfs(root)
return min2 if min2 != inf else -1
貌似我理解题目错了。
Based on the special property of the tree, we can guarantee that the root node is the smallest node in the tree.
- Yangshun
class Solution(object):
def findSecondMinimumValue(self, root):
res = [float('inf')]
def traverse(node):
if not node:
return
if root.val < node.val < res[0]:
res[0] = node.val
traverse(node.left)
traverse(node.right)
traverse(root)
return -1 if res[0] == float('inf') else res[0]
学到闭包写法!如果不使用nonlocal的话!
类似我这样直接暴力,只是没有利用root信息:
def findSecondMinimumValue(self, root):
self.ans = float('inf')
min1 = root.val
def dfs(node):
if node:
if min1 < node.val < self.ans:
self.ans = node.val
elif node.val == min1:
dfs(node.left)
dfs(node.right)
dfs(root)
return self.ans if self.ans < float('inf') else -1
还有就是常规的思路:
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 value same as root value, need to find the next candidate
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);
} else if (left != -1) {
return left;
} else {
return right;
}
}
public int findSecondMinimumValue(TreeNode root)
{
int rootVal = root.val;
int secondSmall =Integer.MAX_VALUE;
boolean diffFound = false;
Queue<TreeNode> Q= new LinkedList<TreeNode>();
Q.add(root);
while(!Q.isEmpty())
{
TreeNode curr=Q.poll();
if(curr.val!=rootVal && curr.val < secondSmall)
{
secondSmall=curr.val;
diffFound=true;
}
if(curr.left!=null)
{
Q.add(curr.left);
Q.add(curr.right);
}
}
return (secondSmall == Integer.MAX_VALUE && !diffFound) ? -1 : secondSmall;
}
标签:Node,Binary,right,node,val,Tree,value,root,left From: https://blog.51cto.com/u_11908275/6380972