二叉搜索树中的众数

题目链接

题目原文 给定一个有相同值的二叉搜索树(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)Q(1),而利用递归实现,虽然没有显式消耗额外空间,递归过程中隐式调用的系统栈也消耗了空间。
Morris算法利用了中序遍历的重要特性,根节点的前驱节点若存在,一定存在于左子树的最右子节点。因此,我们在遍历过程中,需要构建辅助指针,该指针从各父节点的前驱节点指向该节点。
Morris 中序遍历算法的步骤如下:

  1. 如果当前节点的左子节点为空,则遍历当前节点,并将其右子节点作为当前节点。
  2. 如果当前节点的左子节点不为空,在当前节点的左子树中找到当前节点在中序遍历下的前驱节点。
    • 如果前驱节点的右子节点为空,那么需要构建辅助指针,将它的右子节点指向当前节点。继续向左子树遍历,cur=cur.left。
    • 如果前驱节点的右子节点不为空,将它的右子节点置为空(恢复树形状)。遍历当前节点 。 继续遍历右子树,cur=cur.right。
  3. 重复以上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