[LeetCode] 501. Find Mode in Binary Search Tree 解题报告 - 萌萌小七的专栏 - CSDN博客

[LeetCode] 501. Find Mode in Binary Search Tree 解题报告 - 萌萌小七的专栏 - CSDN博客

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).

这个题咋看之下还是有点难度，题意是要我们需找树种出现最多的节点，一开始还真是没有头绪。

经过仔细分析以后，我们会发现，对于本题中的二叉搜索树，节点的排列是有顺序的，左节点<=当前节点<=右节点。也就是说，假设这样一种情况（可能不严谨，但是足够说明问题）：存在大于等于3个的连续相同的节点，且当前节点存在左右子树，那么相同的三个节点一定是：当前节点、左子树中最大的节点和右子树中最小的节点。

这里我们容易想到的是中序遍历（对于整个树，先遍历左节点，再遍历中间节点，最后遍历右节点），使用中序遍历遍历二叉搜索树，可以获得一个从小到大的排好序的升序序列。

分析到这里，题目就转化成了，给定一个升序序列，寻找重复次数最多的数字，这就非常简单了。

代码如下，需要注意的是第20行，是处理遍历完整棵树以后，可能最后一段是相同的且最长的，这样一种情况的。

Read full article from [LeetCode] 501. Find Mode in Binary Search Tree 解题报告 - 萌萌小七的专栏 - CSDN博客