iT邦幫忙

2022 iThome 鐵人賽

DAY 9
0
自我挑戰組

leetcode 30天 不中斷解題挑戰系列 第 9

Day9 leetcode 解題挑戰(Tree,Binary Search)

  • 分享至 

  • xImage
  •  

首先是 589. N-ary Tree Preorder Traversal (easy)
https://leetcode.com/problems/n-ary-tree-preorder-traversal/

這題基本上跟Binary Tree Preorder Traversal 差不多,差異點就只是在於原本只有兩個節點,現在變成很多節點罷了,還是由左至右去進行讀取即可。
這邊寫了兩個做法一個試用recursion去進行讀取,一個是iterative

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution:
    # recursion
    def preorder(self, root: 'Node') -> List[int]:
        result = []
        def preOrderN(root):
            if root is None:
                return 
            result.append(root.val)
            for i in root.children:
                preOrderN(i)
        preOrderN(root)
        return result
    
    #stack + iterative
    def preorder(self, root: 'Node') -> List[int]:
        if root is None:
            return []
        stack = [root]
        result = []
        while stack:
            temp = stack.pop()
            result.append(temp.val)
            stack += temp.children[::-1]
        return result

再來是 102. Binary Tree Level Order Traversal (medium)
https://leetcode.com/problems/binary-tree-level-order-traversal

就level order,基本上就是BFS解,算是必備知識之一。

  1. 首先一定是queue
  2. 先把root放進queue裡,檢查是否有左右節點。
  3. 有的話就放到queue裡,然後把root.val放到答案裡面,持續這過程。
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    #BFS
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if root is None:
            return []
        queue = deque()
        queue.append(root)
        ans =[]
        while queue:
            levelList = []
            for i in range(len(queue)):
                temp = queue.popleft()
                if temp.left:
                    queue.append(temp.left)
                if temp.right:
                    queue.append(temp.right)
                levelList.append(temp.val)
            ans.append(levelList)
        return ans

首先我先寫出以上的東西,但接下來稍微參考了一下其他人的寫法。
發現如果多塞一個變數來計算層數,可以少判斷很多次。

class Solution:
    #BFS進階版本
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        ans = []
        nowlevel = 1
        queue = [(root,1)]#右邊的數字代表該node在哪一個層次
        levelList = []
        while queue:
            temp,level = queue.pop(0)
            if level != nowlevel:#代表進入到下一層
                ans.append(levelList)
                levelList = []
                nowlevel += 1
            if temp:#有可能會是None
                levelList.append(temp.val)
                queue.append((temp.left, level+1))
                queue.append((temp.right, level+1))
        return ans

再來是 704. Binary Search (easy)
https://leetcode.com/problems/binary-search

就真的是Binary Search,所以就快速跳過

class Solution:
    def search(self, nums: List[int], t: int) -> int:
        if t < nums[0] or t > nums[-1]:
            return -1
        l,r = 0,len(nums)-1
        while l <= r:
            mid = l+(r-l)//2
            if nums[mid] == t:
                return mid
            elif nums[mid] <t:
                l = mid + 1
            else:
                r = mid - 1
        return -1
    
    #別人寫法
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1
        while l < r:
            mid = (l + r) // 2
            if nums[mid] >= target:
                r = mid
            else:
                l = mid + 1
        return l if nums[l] == target else -1
    
    #白癡法
    def search(self, nums: List[int], t: int) -> int:
        if t in nums:
            return nums.index(t)
        return -1
    

以上就是今天的練習,感謝大家


上一篇
Day8 leetcode 隨機挑題(String, Greedy, Linked List)
下一篇
Day10 leetcode隨機挑題 (Binary Tree, Binary Search Tree, Binary Search)
系列文
leetcode 30天 不中斷解題挑戰30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言