主題

[LeetCode] 501. Find Mode in Binary Search Tree - 二元樹(shù)追蹤

テリ君(桃夫模式) | 2023-11-01 19:42:17 | 巴幣 0 | 人氣 126

Code:

#Definition for a binary tree node.
from collections import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def findMode(self, root:TreeNode) -> [int]:
        # make an array to create a tree.
        self.inorder = []
        # define a private func, append the whole tree into the array
        def preorderTraversal(root):
            if not root: return
            self.inorder.append(root.val)
            preorderTraversal(root.left)
            preorderTraversal(root.right)
        preorderTraversal(root)
        # using collections.Counter to count the freq
        freq = Counter(self.inorder)
        # get the maximum
        maximum = max(freq.values())
        # get all the freq vals that == maximum
        return [x for x in freq if freq[x] == maximum]

## traversal 追蹤
# inorder traversal : travel to left then root then right
# preorder traversal : travel to root then left to right
# postorder traversal : travel to left to right to root

## Complexity
# Time:O(n)
# Space:O(n)

root = TreeNode(1)
root.right = TreeNode(2)
root.left = TreeNode(2)

root2 = TreeNode(0)

sol = Solution()
print(sol.findMode(root))
print(sol.findMode(root2))

其實(shí)這題我覺(jué)得前中後序應(yīng)該都沒(méi)差

剛好今天資結(jié)也在教

也太巧= =

下面是可以在輸入樹(shù)後
以陣列形式印出前序中序後序的小工具

我只是懶得動(dòng)腦所以做這個(gè)

不然其實(shí)人工辨識(shí)可能更快

輸入樹(shù)的速度太慢了

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Traversal:
    def findMode(self, root, mode): # 1 inorder 2 preorder 3 postorder
        order = []
        if mode == 1:
            order = Traversal.inorder(root, order)
        if mode == 2:
            order = Traversal.preorder(root, order)
        if mode == 3:
            order = Traversal.postorder(root, order)
        return order

    def inorder(root, order):
        if not root:
            return
        Traversal.inorder(root.left, order)
        order.append(root.val)
        Traversal.inorder(root.right, order)
        return order
    def preorder(root, order):
        if not root:
            return
        order.append(root.val)
        Traversal.preorder(root.left, order)
        Traversal.preorder(root.right, order)
        return order
    def postorder(root, order):
        if not root:
            return
        Traversal.postorder(root.left, order)
        Traversal.postorder(root.right, order)
        order.append(root.val)
        return order

# tree here
root = TreeNode('a')
root.left = TreeNode('b')
root.right = TreeNode('c')
root.left.left = TreeNode('d')
root.left.right = TreeNode('e')
root.left.right.left = TreeNode('g')
root.right.left = TreeNode('f')
root.right.left.right = TreeNode('h')

sol = Traversal()
print(sol.findMode(root, 1))
print(sol.findMode(root, 2))
print(sol.findMode(root, 3))