3 Python solutions: recur/iter inorder, and preorder. O(n)/O(log(n))


  • 0
    A
    class Solution1(object):
        def getMinimumDifference(self, root):
            """
            :type root: TreeNode
            :rtype: int
            Recursive inorder tree walk. Time: O(n) Space: O(log(n))
            """
            def inorder(node, pre, res):
                """
                """
                if node is None:
                    return pre, res
                pre, res = inorder(node.left, pre, res)
                res = min(res, node.val - pre)
                pre = node.val
                pre, res = inorder(node.right, pre, res)
                return pre, res
            pre, res = inorder(root, -float('inf'), float('inf'))
            return res
    
    
    class Solution2(object):
        def getMinimumDifference(self, root):
            """
            :type root: TreeNode
            :rtype: int
            Iterative inorder tree walk with a stack. Time: O(n) Space: O(log(n))
            """
            pre, res = -float('inf'), float('inf')
            node = root
            stk = []
            while node or stk:
                while node:
                    stk.append(node)
                    node = node.left
                node = stk[-1]  # step back from NIL node
                res = min(res, stk.pop().val - pre)
                pre = node.val
                node = node.right
            return res
    
    
    class Solution3(object):
        def getMinimumDifference(self, root):
            """
            :type root: TreeNode
            :rtype: int
            Recursive preorder tree walk. Time: O(n) Space: O(log(n))
            """
            def preorder(node, pred, succ, res):
                """
                At each recursion, ignore node's subtree and compare node with its
                current predecessor and current successor.
                :param pred: current predecessor of node if ignoring its subtree
                :param succ: current successor of node if ignoring its subtree
                """
                if node is None:
                    return res
                res = min(res, node.val - pred)
                res = min(res, succ - node.val)
                res = preorder(node.left, pred, node.val, res)
                res = preorder(node.right, node.val, succ, res)
                return res
            return preorder(root, -float('inf'), float('inf'), float('inf'))
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.