LeetCode: 501. Find Mode in Binary Search Tree

题目

原题地址：https://leetcode.com/problems/find-mode-in-binary-search-tree/

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 中值出现次数最多的节点。

中序遍历统计各个值出现的次数，然后找出次数最多的节点

通过 BST 的特性可以知道，中序遍历 BST 的过程类似于按节点值从小到大进行遍历的过程，因此相同的值会是连续出现，这样就可以在中序遍历的过程中快速统计所有值出现的次数，不需要反复遍历去统计。

中序遍历的 Python 代码类似这样:

def inorder(root):
    if root is None:
        return
    inorder(root.left)

    # print(root)

    inorder(root.right)

这个方法的 Python 代码类似下面这样:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findMode(self, root):
        self.count = 0
        self.count_val = None
        self.max_count = 0
        self.vals = []

        self.inorder(root)
        return self.vals

    def inorder(self, root):
        if root is None:
            return

        self.inorder(root.left)

        if self.count_val is None:
            self.count_val = root.val
        if self.count_val == root.val:
            self.count += 1
        else:
            self.count_val = root.val
            self.count = 1

        if self.count > self.max_count:
            self.max_count = self.count
            self.vals.clear()

        if self.count == self.max_count:
            self.vals.append(root.val)

        self.inorder(root.right)

Comments