首先是 113. Path Sum II (medium)
https://leetcode.com/problems/path-sum-ii/

這題會給予一個Binary Tree以及一個targetSum，需要把所有的root-leaf只要總和為targetSum的路線進行輸出。

想法上很簡單

1. 建立基本的遍歷方式
2. 添加一個path變數用來記錄所走過的路線
3. 當遇到左右child都是None的時候，判斷path的總和是否為targetSum，是的話就儲存。

# 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:
#     #1. 每次往下都要做紀錄
#     #2. 只要是不同條線，就算值都相同也要記錄
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        if root is None:
            return []
        if root.left is None and root.right is None:
            return [[root.val]] if root.val == targetSum else []
        result = []
        def dfs(root,path):
            flag = 0
            temp = path.copy()#如果用list儲存，這邊會是個坑，之前踩過
            temp.append(root.val)
            if root.left:
                dfs(root.left,temp)
            else:
                flag +=1
            if root.right:
                dfs(root.right,temp)
            else:
                flag +=1
            if flag == 2 and sum(temp) == targetSum:
                result.append(temp)
        dfs(root,[])
        return result

這邊是第一種寫法，比較沒經過整理，所以有點亂七八糟，反正就是缺什麼補什麼。

# 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:
#     #1. 每次往下都要做紀錄
#     #2. 只要是不同條線，就算值都相同也要記錄
#     #略微調整
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        if root is None:
            return []
        if root.left is None and root.right is None:
            return [[root.val]] if root.val == targetSum else []
        result = []
        def dfs(root,path):
            # flag = 0
            if root is None:
                return
            temp = path.copy()#如果用list儲存，這邊會是個坑，之前踩過
            temp.append(root.val)
            if root.left is None and root.right is None and sum(temp) == targetSum:
                result.append(temp)
            dfs(root.left,temp)
            dfs(root.right,temp)  
        dfs(root,[])
        return result

稍微調整後大致上長這樣，把沒必要的flag砍掉。

再來是 278. First Bad Version (easy)
https://leetcode.com/problems/first-bad-version

題目會提供一個api叫做isBadVersion(version)，可以判斷該version的值為True還是False。
接著他會提供一個叫做versions的串列，裡面儲存[1,2,3........,n]的version。必須找到，第一個由False轉成True的version。
EX:
isBadVersion(3) return False
isBadVersion(4) return True-> 第一個由False轉成True的version的是4，所以答案就是4
基本上這題就是要用Binary Search，但理所當然的先用Linear Search試試看吧

# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:

class Solution:
    # Linear Search測試一下題目，果然TLE
    def firstBadVersion(self, n: int) -> int:
        i = 0
        while 1:
            if isBadVersion(i):
                return i
            i+=1

毫不意外TLE，能過我反而訝異
接下來就是正常的Binary Search

# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:
class Solution:
    #binary第一版本，先找到True然後檢查前一個是不是False
    def firstBadVersion(self, n: int) -> int:
        l,r = 1,n
        while l<=r:
            mid = l+(r-l)//2
            if isBadVersion(mid):
                if isBadVersion(mid-1):
                    r = mid-1
                else:
                    return mid
            else:
                l = mid+1

這方法呢，就是直接去找True在哪，找到True之後，檢查前一個是不是False，不是的話繼續找。但這樣做其實很浪費時間，所以又有了一點小改動。

# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:

class Solution:
    #稍微做個修正，找False也找True，增加找到的機率減少迴圈的次數
    def firstBadVersion(self, n: int) -> int:
        l,r = 1,n
        while l<=r:
            mid = l+(r-l)//2
            if isBadVersion(mid):
                if isBadVersion(mid-1):
                    r = mid-1
                else:
                    return mid
            else:
                if isBadVersion(mid+1):
                    return mid+1
                else:
                    l = mid+1

除了找True以外也找False，找到False就檢查False的下一個，找到True就檢查True的上一個，以減少迴圈的執行次數。

接下來是 98. Validate Binary Search Tree (medium)
https://leetcode.com/problems/validate-binary-search-tree/

簡單來說，檢查這是否是合法的BST。
最簡單的方式就是Inorder Traversal(中序遍歷)，直接把所有值抓下來，sort後看跟原本抓下來的一不一樣。
(中序遍歷可以直接把樹拍扁變成一條線，如果他是BST就會剛好按照大小順序排好)

# 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 isValidBST(self, root: Optional[TreeNode]) -> bool:
        result = []
        def inOrderTraversal(root):
            if root is None:
                return
            inOrderTraversal(root.left)
            result.append(root.val)
            inOrderTraversal(root.right)
        inOrderTraversal(root)
        # print(result)
        if len(result) != len(set(result)):
            return 0
        return result == sorted(result)

但老實說這樣會多花一些效能，除非是真的想不到辦法，平常應該不會這樣寫

接著就是一邊visit時一邊進行比較，因為BST的特性，小的值一定在左邊，大的值一定在右邊。
1.假設minVal跟maxVal
2.如果是往right走，那原先的root.val就會是minVal，right以下的所有值都不可以比root.val大(這是定義)
3.left亦同。

# 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 isValidBST(self, root: Optional[TreeNode]) -> bool:
        def dfs(root,minVal = -float("inf"),maxVal = float("inf")):
            if root is None:
                return 1
            if minVal>= root.val or maxVal <=root.val:
                return 0
            #往左走最大值就會是parent.val，往右走最小值就是parent.val
            return dfs(ro

所以最後就會變成這樣

以上就是今天的練習，感謝大家觀看。