难度: Easy
原题连接
内容描述
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).
Note: There are at least two nodes in this BST.
思路 1 - 时间复杂度: O(N)- 空间复杂度: O(N)******
inorder遍历BST已经有序,只需要算所有相邻两个数的差的绝对值就可以了,不需要两轮遍历
class Solution:
def getMinimumDifference(self, root):
"""
:type root: TreeNode
:rtype: int
"""
vals = []
def inorder(root):
if not root:
return
inorder(root.left)
vals.append(root.val)
inorder(root.right)
inorder(root)
return min(abs(vals[i] - vals[i-1]) for i in range(1, len(vals))) # vals is already sorted in BST