Manjusaka

11-01 leetcode 0501

链接 501. Find Mode in Binary Search Tree

题目

Given the root of a binary search tree (BST) with duplicates, return all the mode(s) (i.e., the most frequently occurred element) in it.

If the tree has more than one mode, return them in any order.

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.

题解

这题直接写很好写，但是 follow up 要求 O1 时间，就很笑嘻了，

这里需要用一种特殊的遍历方法，Morris Traversal，这个方法可以在 O1 的空间复杂度下的遍历二叉树

记作当前节点为cur。

1. 如果cur无左孩子，cur向右移动（cur=cur.right）
2. 如果cur有左孩子，找到cur左子树上最右的节点，记为mostright
   1. 如果mostright的right指针指向空，让其指向cur，cur向左移动（cur=cur.left）
   2. 如果mostright的right指针指向cur，让其指向空，cur向右移动（cur=cur.right）

from typing import Optional


class TreeNode:
    def __init__(
        self,
        val: int = 0,
        left: Optional["TreeNode"] = None,
        right: Optional["TreeNode"] = None,
    ):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def findMode(self, root: Optional["TreeNode"]) -> list[int]:
        current_node = root
        result = []
        current_count, current_value, max_count = 0, 10**6, 0
        while current_node:
            if current_node.left:
                neighbor = current_node.left
                while neighbor.right:
                    neighbor = neighbor.right
                neighbor.right = current_node
                current_node.left, current_node = None, current_node.left
            else:
                if current_node.val == current_value:
                    current_count += 1
                else:
                    current_count, current_value = 0, current_node.val
                if current_count == max_count:
                    result.append(current_value)
                elif current_count > max_count:
                    result, max_count = [current_value], current_count
                current_node = current_node.right
        return result