[LeetCode]530. Minimum Absolute Difference in BST

题目

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.

难度

Easy

方法

对于BST，采用中序遍历，就会将节点按照从小到大遍历出来。依次取2个节点的差值，然后取最小值即可

python代码

import sys

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    def __init__(self):
        self.minValue = sys.maxint
        self.list = []

    def getMinimumDifference(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.traverse(root)
        return self.minValue

    def traverse(self, node):
        if node.left:
            self.traverse(node.left)
        if self.list:
            self.minValue = min(self.minValue, node.val-self.list.pop())
        self.list.append(node.val)
        if node.right:
            self.traverse(node.right)

root = TreeNode(1)
root.right = TreeNode(5)
root.right.left = TreeNode(2)
assert Solution().getMinimumDifference(root) == 1