二叉搜索树最小差值

# -*- coding: utf-8 -*-


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


class BT(object):
    def __init__(self):
        self.root = None

    def levelOrderToBT(self, nums):
        n = len(nums)

        if n > 0:
            self.root = TreeNode(nums[0])
            queue, idx = [self.root], 1
            while queue and idx < n:
                node = queue.pop(0)
                node.left = TreeNode(nums[idx]) if nums[idx] != None else None
                if node.left:
                    queue.append(node.left)
                node.right = TreeNode(nums[idx + 1]) \
                    if idx + 1 < n and nums[idx + 1] != None else None
                if node.right:
                    queue.append(node.right)
                idx += 2
        return self.root

    @staticmethod
    def levelOrder(root):
        if not root:
            return []

        queue, res = [root], []
        while queue:
            node = queue.pop(0)
            if node:
                res.append(node.val)
                queue.append(node.left)
                queue.append(node.right)
            else:
                res.append(None)
        while res and res[-1] == None:
            res.pop()

        return res


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param root TreeNode类
# @return int整型
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/f8ac976b49bd450887b9281f315186c7?tpId=196&tqId=40504&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D8%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=
    算法：
        中序遍历二叉树，使用self.pre记录当前节点的前驱节点的val，不断更新差值diff与self.pre
    复杂度：
        时间复杂度：O(N)，N为节点数
        空间复杂度：O(H), H为树的高度
    """

    def minDifference(self, root):
        # write code here
        def inOrder(root):
            if root:
                inOrder(root.left)
                if self.pre == -1:
                    self.pre = root.val
                else:
                    self.diff = min(self.diff, abs(root.val - self.pre))
                    self.pre = root.val
                inOrder(root.right)

        self.diff, self.pre = 10 ** 9, -1

        inOrder(root)

        return self.diff


if __name__ == "__main__":
    sol = Solution()

    nums = [2, 1, 3, None, None, None, 4]

    # nums = [3, 1, 5, None, None, None, 9]

    # nums = [9, 4, 16, 1, 7, 11, 19]

    bt = BT()
    bt1 = bt.levelOrderToBT(nums)
    # print BT.levelOrder(bt1)

    res = sol.minDifference(bt1)
    print res