【Leetcode】501. Find Mode in Binary Search Tree 解题报告

在一棵二叉排序树（非严格定义）中查找出现最多的数字（s）

思路

对于二叉树的遍历有三种方式，先序后序中序，而这道题一定要用中序遍历，因为只有中序遍历才能将当前节点的值既算在左子树中又算在右子树中，不会因为访问了左子树而对右子树造成影响。

方法1 使用字典作为辅助空间（不满足要求 ）

class Solution1:
    def findMode(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        if root == None:
            return res
        self.dictionary = {}
        self.maxer = 0
        self.DFS(root)
        for key in self.dictionary:
            if self.dictionary[key] == self.maxer:
                res.append(key)
        return res

    def DFS(self, root):
        if root.val in self.dictionary:
            self.dictionary[root.val] +=1
        else:
            self.dictionary[root.val] = 1
        self.maxer = max(self.maxer, self.dictionary[root.val])
        if root.left:
            self.DFS(root.left)
        if root.right:
            self.DFS(root.right)

方法2 中序遍历递归 栈+O(1)辅助变量

class Solution2:
    def findMode(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        self.currMode = 0
        self.currCount = 0
        self.maxCount = 0
        self.modeCount = 0
        self.res = []
        self.DFS(root)
        return self.res[:self.modeCount]

    def Handle(self, val):
        if val != self.currMode:
            self.currMode  = val
            self.currCount = 0
        self.currCount +=1
        if self.currCount >= self.maxCount:
            if self.currCount == self.maxCount:
                self.modeCount +=1
            else:
                self.maxCount = self.currCount
                self.modeCount = 1
            if len(self.res) < self.modeCount:
                self.res.append([-1])
            self.res[self.modeCount-1] =  val

    def DFS(self, root):
        if root == None:
            return
        self.DFS(root.left)
        self.Handle(root.val)
        self.DFS(root.right)

方法3 中序遍历非递归 栈+O(1)辅助变量

class Solution3:
    def findMode(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if root == None:
            return []
        stack = []
        pNode = root
        currMode, currCount, modeCount, maxCount, res = 0,0,0,0,[]
        while(len(stack) or pNode):
            if pNode:
                stack.append(pNode)
                pNode = pNode.left
            else:
                pNode = stack.pop()
                if pNode.val != currMode:
                    currCount = 0
                    currMode = pNode.val
                currCount +=1
                if currCount >= maxCount:
                    if currCount == maxCount:
                        modeCount += 1
                    else:
                        modeCount = 1
                        maxCount = currCount
                    if len(res) < modeCount:
                        res.append(-1)
                    res[modeCount -1] = currMode
                pNode = pNode.right
        return res[:modeCount]

方法4 Morris中序遍历算法 仅O(1)辅助变量

class Solution4:
    def findMode(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """

        if root == None:
            return []
        pNode = root
        self.currMode, self.currCount, self.modeCount, self.maxCount, self.res = 0, 0, 0, 0, []

        def handle(val):
            if val != self.currMode:
                self.currMode = val
                self.currCount = 0
            self.currCount +=1
            if self.currCount >= self.maxCount:
                if self.currCount == self.maxCount:
                    self.modeCount +=1
                else:
                    self.maxCount = self.currCount
                    self.modeCount =1
                if len(self.res) < self.modeCount:
                    self.res.append(-1)
                self.res[self.modeCount-1] = val

        while(pNode):
            if pNode.left == None:
                handle(pNode.val)
                pNode = pNode.right
            else:
                tmp = pNode.left
                while(tmp.right and tmp.right != pNode):
                    tmp = tmp.right
                if tmp.right == None:
                    tmp.right = pNode
                    pNode =  pNode.left
                else:
                    handle(pNode.val)
                    pNode = pNode.right
        return self.res[:self.modeCount]