Find Mode in Binary Search Tree

此题如果没有额外空间的要求，利用哈希表我们就可以搞定

class Solution(object):
    def findMode(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []

        store = collections.Counter()
        self.inOrder(root, store)
        base = max(store.values())
        result = []
        for key, value in store.iteritems():
            if value == base:
                result.append(key)
        return result

    def inOrder(self, root, store):
        if not root:
            return 

        self.inOrder(root.left, store)
        store[root.val] += 1
        self.inOrder(root.right, store)

如果要O（1）空间，则利用Morris traversal中序遍历，第一遍找出现最多的次数，第二遍把符合这个次数的点收集起来

class Solution(object):
    maxCount = 0

    def findMode(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        if not root.left and not root.right:
            return [root.val]
        result = []
        self.inOrder(root, 0, result)
        self.inOrder(root, 1, result)
        return result

    def inOrder(self, root, status, result):
        if not root:
            return 

        pre, cur = root, None
        tmp, tmpValue = 0, -sys.maxint
        while pre:
            cur = pre.left
            if cur:
                while cur.right and cur.right != pre:
                    cur = cur.right
                if not cur.right:
                    cur.right = pre
                    pre = pre.left
                    continue
                else:
                    cur.right = None
            if not status:
                if tmpValue != pre.val:
                    tmpValue = pre.val
                    tmp = 1
                else:
                    tmp += 1
                self.maxCount = max(self.maxCount, tmp)
            else:
                if tmpValue != pre.val:
                    tmpValue = pre.val
                    tmp = 1
                else:
                    tmp += 1
                if tmp == self.maxCount:
                    result.append(tmpValue)

            pre = pre.right