Leetcode 530


  Posted on 28 Feb 2017
binary search tree


Tutorial

The in-order of a BST is the increasing order of its nodes. So we just find the in-order of the tree and get the minimum distance of two adjacent nodes.

Solution

from collections import deque

class Solution(object):
    def getMinimumDifference(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.q = deque()
        self.ans = float("inf")
        self.dfs(root)
        return self.ans
    
    def dfs(self, root):
        if not root:
            return
        self.dfs(root.left)
        self.q.append(root.val)
        if len(self.q) > 2:
            self.q.popleft()
        self.update()
        self.dfs(root.right)
    
    def update(self):
        if len(self.q) != 2:
            return
        self.ans = min(self.ans, abs(self.q[0] - self.q[1]))