Leetcode 501. Find Mode in Binar

题目

Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST.

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than or equal to the node's key.
• The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
• Both the left and right subtrees must also be binary search trees.

For example:

Given BST `[1,null,2,2]`,
  1
    \
     2
    /
   2
return `[2]`.

Note: If a tree has more than one mode, you can return them in any order.
Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).

解析

此题是求BST（二叉搜索树）中出现次数最多的值，如果出现多个，都返回结果，顺序不做限定。
作者在使用C语言解决此题时，在IDE中运行无误，提交至leetcode后一直报runtime error，但又从中发现不到什么错误。所以就使用python编写此题。
其思路都是一致的，首先使用DFS将所有的元素出现的次数统计一下，放入dict中。然后再遍历此dict，找到其出现的次数，将出现次数最多的放入返回的array中。

代码（Python）

from collections import defaultdict


# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution(object):
    def findMode(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        counts = defaultdict(int)
        stack = []
        curr = root

        # DFS
        while True:
            while curr:
                stack.append(curr)
                counts[curr.val] += 1
                curr = curr.left

            if len(stack) == 0:
                break

            curr = stack.pop()
            curr = curr.right

        # Find all modes
        mode = -1
        curr_modes = []
        for c in counts:
            if counts[c] == mode:
                curr_modes.append(c)
            if counts[c] > mode:
                mode = counts[c]
                curr_modes = [c]

        return curr_modes

defaultdict是默认的dict，如果访问的元素没有则返回空而不会报错。提交时将该包导入。