首先是 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解,算是必備知識之一。
# 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
以上就是今天的練習,感謝大家