leetcode 530. Minimum Absolute Difference in BST
#coding=utf-8
'''
Given a binary search tree with non-negative values,
find the minimum absolute difference between values of any two nodes.
Example:
Input:
1
\
3
/
2
Output:
1
Explanation:
The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).
'''
#其实简单的思路就是遍历这个二叉树的所有节点的值，然后进行排序，取相邻两个数差最小，最小的差就是所求的结果
# 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 getMinimumDifference(self, root):
"""
:type root: TreeNode
:rtype: int
"""
queue=[root];l=[root.val]
while queue:
node=queue.pop()#node等于退出的一个节点
if node.left:
queue.append(node.left)
l.append(node.left.val)
if node.right:
queue.append(node.right)
l.append(node.right.val)
answer=[];sortedl=sorted(l)
for i in range(1,len(sortedl)):
answer.append(sortedl[i]-sortedl[i-1])
return min(answer)
t=TreeNode(8)
t.left=TreeNode(3);t.right=TreeNode(10)
s=Solution()
print s.getMinimumDifference(t)
转载请注明原文地址: https://ju.6miu.com/read-32933.html
