python morris tree traversal


  • 0
    Z
    class Solution(object):
        
        
        def findMode(self, root):
            """
            :type root: TreeNode
            :rtype: List[int]
            """
            self.prev, self.count, self.maximum, self.res = None, 0, 0, []
            if not root: return []
            def update_count(val):
                if val == self.prev:
                    self.count += 1
                else: # val != prev
                    if self.prev is not None:
                        if self.count == self.maximum:
                            self.res.append(self.prev)
                        elif self.count > self.maximum:
                            self.res = [self.prev]
                    self.maximum = max(self.count, self.maximum)
                    self.prev = val
                    self.count = 1
            
            while root:
                if not root.left:
                    update_count(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:
                        pred.right = None
                        update_count(root.val)
                        root = root.right
            if self.count > self.maximum:
                return [self.prev]
            if self.count == self.maximum:
                return self.res + [self.prev]
            return self.res
    

Log in to reply
 

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