最後一天，我們繼續做幾題相對簡單的LeetCode練習題吧!挑選的題目主要都是前面文章涵蓋的主題，如果有不熟的部分，可以回去看前面幾天的文章。然後答案沒有一定，大家寫自己習慣的寫法就可以囉~(還是提醒一下，下面的程式碼是只能在leetcode跑，如果想拿去vscode跑，記得改相關的參數。)

Binary Search Tree
LeetCode 230 Kth Smallest element in a BST
題目是說給定一個二元搜尋樹的根(root)，還有一個整數k，找到這個二元搜尋樹第k小的值
e.g. Input: root = [3,1,4,null,2], k = 1
Output: 1
e.g. Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3
那回憶一下我們之前說的二元搜尋樹的規則，最左下角的node會有最小值，我們需要從最小值開始看，因此我們可以用stack來處理這個問題，將最小值拋出來後，k-1，再拋它的parent出來，然後查看它有沒有right child，有的話裝進stack裡，沒有的話再拋出stack裡之前存的前一個節點，直到k值為0。

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        stack=[]
        while True:
            while root:
                stack.append(root)
                root=root.left
            root=stack.pop()
            k-=1
            if k==0:
                return root.val
            root=root.right

Topological Sort
LeetCode 207 Course Schedule
題目說總共必須修numCourses(一個整數)的課(總共也只有numCourses的課，所以是把課修完的意思)，標記成0到numCourses-1。給定一個陣列叫prerequisites，中文翻譯作預修課，格式如下:prerequisites[i]=[ai,bi]，意思是要修過bi才能修ai，如果這個prerequisites的陣列是合理的，你會有辦法修完所有課，並return True。否則return False。LeetCode他給了兩個例子:
Input: numCourses = 2, prerequisites = [[1,0]]
Output: True
Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: False (因為總共才兩門課，彼此是彼此的預修，根本無法開始修課)
那我們可以先把整個課表用adjacent list的方式做成有向圖，並且把每門課的必修課數紀錄下來(有些課可能需要你預修三四門課)，並製作一個Queue，將不需要先修任何課的課程先enqueue上，然後每修完一門課(deque)，將numCourses-1，並將需要這門課的課程的必修課數-1，它其必修課數歸0時，將它queue上(代表可以修了)，直到整個queue走完。我們直接看程式碼可能比較清楚:

from collections import deque, defaultdict
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
    # 建立一個preneed的list，index就會是它的課程代碼，value為它還需要先修多少課
    # 根據prerequisites的內容建立adjacent list
        preneed=[0]*numCourses
        coursedict=defaultdict(list)
        for item in prerequisites:
            coursedict[item[1]].append(item[0])
            preneed[item[0]]+=1
   # 找出不需要任何預修課的課，enque在customQ上
        customQ=deque()
        for i in range(len(preneed)):
            if preneed[i]==0:
                customQ.append(i)
   #每次修一門課將numCourses-1，並更新preneed list的參數
        while len(customQ)!=0:
            take_course=customQ.popleft()
            numCourses-=1
            for course_index in coursedict[take_course]:
                preneed[course_index]-=1
                if preneed[course_index]==0:
                    customQ.append(course_index)
   # 最後有修完就是0 return True，沒有就是False
        if numCourses!=0:
            return False
        else:
            return True

DFS(Depth First Search，深度優先搜尋)
LeetCode 543 Diameter of Binary Tree
給定二元樹的根(root)，寫一個function回傳樹的直徑(diameter)。這裡直徑指的是樹的兩點間找最長距離(距離為兩節點間的edge(邊)總數)，這個路徑可以不必經過root。舉例來說(leetcode的例子):
Input: root = [1,2,3,4,5]
Output: 3
Reason: 3 is the length of the path [4,2,1,3] or [5,2,1,3].
Input: root = [1,2]
Output: 1
那一開始想法會是，我們可以藉由算左右節點的高度(1+max(left,right))，然後將左右節點相加(left+right)來得到直徑(diameter)，但問題會出在當樹的子樹很寬的時候，最長路徑不通過root的時候，最長路徑不會是root的左右子樹高相加，因此我們需要一個參數self.diameter記得在整個過程中，所記錄到最長的路徑(某個節點的左右子樹相加)。

# 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:
    def helper(self,root:Optional[TreeNode])->int:
        if not root:
            return 0
        left=self.helper(root.left)
        right=self.helper(root.right)
        self.diameter=max(self.diameter,left+right)
        return 1+max(left,right)
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.diameter=0
        self.helper(root)
        return self.diameter

BFS(Breadth First Search，廣度優先搜尋)
LeetCode 102 Binary Level Order Traversal
給定一個根(root)，用level order traversal的方式回傳list，相同level的節點必須被包在同一層list中
e.g.
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]
那和前面文章不太一樣的是，我們前面不需要將不同層的分開，所以這邊我們可以用list或是dictionary紀錄層級(level)，然後每層有list，用index/pointer去指向現在在看的節點。

# list的寫法
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if root==None:
            return []
        else:
            level=0
            temp=[]
            temp.append([root])
            index=0
            while index<len(temp[level]):
                if len(temp)<level+2:
                    temp.append([])
                node=temp[level][index]
                if node.left is not None:
                    temp[level+1].append(node.left)
                if node.right is not None:
                    temp[level+1].append(node.right)
                temp[level][index]=node.val
                index+=1
                if index==len(temp[level]):
                    level+=1
                    index=0
            temp.pop()
            return temp

當然也能換成dictionary:

from collections import defaultdict
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if root==None:
            return []
        else:
            level=0
            temp=defaultdict(list)
            temp[level].append(root)
            index=0
            while index<len(temp[level]):
                node=temp[level][index]
                if node.left is not None:
                    temp[level+1].append(node.left)
                if node.right is not None:
                    temp[level+1].append(node.right)
                temp[level][index]=node.val
                index+=1
                if index==len(temp[level]):
                    level+=1
                    index=0
            temp.pop(level)
            return temp.values()

差不多差不多，剩下大家就自己試試囉~~