二叉搜索树中的众数

题目链接

题目原文

给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。

假定 BST 有如下定义：

结点左子树中所含结点的值小于等于当前结点的值
结点右子树中所含结点的值大于等于当前结点的值
左子树和右子树都是二叉搜索树

例如：
给定 BST [1,null,2,2],

1
  \
   2
  /
2
返回[2].

提示：如果众数超过1个，不需考虑输出顺序

进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）

题目解析

找出二叉搜索树中的众数，由二叉搜索树的性质，左子节点小于等于父节点，右子节点大于等于父节点，二叉搜索树的中序遍历，将会输出树中所有值从小到大的排列，在此过程中就可以统计每个数的出现次数。

解题方法

结果保存

由于我们可以从小到大顺序遍历树中的值，相同的值一定连续遍历，所以只需要判断两次遍历的值是否相同，进而计数，并保存当前出现次数最大的出现频次。

# 输入：数字
def update(num):
            nonlocal cur_val,count,max_count,result
            # print(cur_val,count,max_count,result)
            if num ==cur_val:
                count+=1
            else:
                count=1
                cur_val=num
            if count==max_count:
                result.append(num)
            if count>max_count:
                max_count=count
                result=[cur_val]

中序遍历

中序遍历的递归实现代码也较为简单，不多赘述，代码如下:

class Solution:
    def findMode(self, root: TreeNode) -> List[int]:
        cur_val=count=max_count=0
        result=[]
        def update(num):
            nonlocal cur_val,count,max_count,result
            # print(cur_val,count,max_count,result)
            if num ==cur_val:
                count+=1
            else:
                count=1
                cur_val=num
            if count==max_count:
                result.append(num)
            if count>max_count:
                max_count=count
                result=[cur_val]
        def inOrder(node):
            if node is None:
                return 
            # 先遍历左子节点
            inOrder(node.left)
            # 遍历当前节点
            update(node.val)
            # 最后遍历右子节点
            inOrder(node.right)
        inOrder(root)
        return result

Morris算法

Morris算法利用辅助指针，将中序遍历所需要的空间复杂度降为 $Q(1)$ ，而利用递归实现，虽然没有显式消耗额外空间，递归过程中隐式调用的系统栈也消耗了空间。
Morris算法利用了中序遍历的重要特性，根节点的前驱节点若存在，一定存在于左子树的最右子节点。因此，我们在遍历过程中，需要构建辅助指针，该指针从各父节点的前驱节点指向该节点。
Morris 中序遍历算法的步骤如下：

如果当前节点的左子节点为空，则遍历当前节点，并将其右子节点作为当前节点。
如果当前节点的左子节点不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点。
- 如果前驱节点的右子节点为空，那么需要构建辅助指针，将它的右子节点指向当前节点。继续向左子树遍历，cur=cur.left。
- 如果前驱节点的右子节点不为空，将它的右子节点置为空（恢复树形状）。遍历当前节点 。继续遍历右子树，cur=cur.right。
重复以上1，2步，直到当前节点为空。

图示

class Solution:
    def findMode(self, root: TreeNode) -> List[int]:
        cur_val=count=max_count=0
        result=[]
        def update(num):
            nonlocal cur_val,count,max_count,result
            # print(cur_val,count,max_count,result)
            if num ==cur_val:
                count+=1
            else:
                count=1
                cur_val=num
            if count==max_count:
                result.append(num)
            if count>max_count:
                max_count=count
                result=[cur_val]
        #morris
        cur=root
        while cur:
            if not cur.left:
                # 遍历这个节点
                update(cur.val)
                cur=cur.right
                continue
            pre = cur.left
            while pre.right and pre.right != cur:
                pre=pre.right
            if not pre.right:
                pre.right=cur
                cur=cur.left
            else:
                pre.right=None
                # 遍历这个节点
                update(cur.val)
                cur = cur.right
        return result

总结

二叉搜索树题目，一般会利用到二叉搜索树的性质，见到时可以考虑如何利用。

参考

https://leetcode-cn.com/problems/find-mode-in-binary-search-tree/solution/er-cha-sou-suo-shu-zhong-de-zhong-shu-by-leetcode-/
https://www.cnblogs.com/anniekim/archive/2013/06/15/morristraversal.html

【刷题】二叉搜索树中的众数-Morris遍历