LC-0501 Easy LeetCode

501. Find Mode in Binary Search Tree

Tree Depth-First Search Binary Search Tree Binary Tree

Read the full problem statement on LeetCode.

Difficulty: easy Acceptance: 57% Topics: Tree, Depth-First Search, Binary Search Tree, Binary Tree

Reading material

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(h)

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

            prev, cnt, max_cnt = inorder(root.left, prev, cnt, max_cnt, result)
            if prev:
                if root.val == prev.val:
                    cnt += 1
                else:
                    cnt = 1
            if cnt > max_cnt:
                max_cnt = cnt
                del result[:]
                result.append(root.val)
            elif cnt == max_cnt:
                result.append(root.val)
            return inorder(root.right, root, cnt, max_cnt, result)

        if not root:
            return []
        result = []
        inorder(root, None, 1, 0, result)
        return result

Solution from kamyu104/LeetCode-Solutions · MIT