Python O(n) time O(1) space, morris tree traversal


  • 0
    Z
    class Solution(object):
        
        def getMinimumDifference(self, root):
            minimum, prev = float("inf"), -float("inf")
            while root:
                if not root.left:
                    minimum = min(minimum, root.val - prev)
                    prev = root.val
                    root = root.right
                else:
                    pred = root.left
                    while pred.right and pred.right is not root:
                        pred = pred.right
                    if not pred.right:
                        pred.right = root
                        root = root.left
                    else:
                        minimum = min(minimum, root.val - prev)
                        prev = root.val
                        pred.right = None
                        root = root.right
            return minimum
    

Log in to reply
 

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