嗨大家好，今天要介紹的主題是binary tree。當初在leetcode要練習這個主題時，覺得就是左子樹、右子樹、遞迴，應該很簡單吧。寫了後才發現，這是我最讓我苦惱的章節。今天想分享幾題我覺得很靈活的題目給大家看。

Leetcode 101. Symmetric Tree

題目敘述：給予某個二元樹的root，判斷這顆二元樹是否以root為中線左右對稱。

Exaple:

(圖源：Leetcode)

上述的圖顯示這個二元樹是有對稱以root為中線的，回傳True。

分析：

• 我們需要去同時對左子樹和右子樹做DFS。
• 如果只有某邊的子樹，就代表對成不成立。
• 左子樹的root的value要等於右子樹root的value
• 之後要比較(左子樹.left, 右子樹.right)
• 之後要比較(左子樹.right, 右子樹.left)

上圖，想像要把左子樹以root當作對稱線翻過去，看看是否能和右子樹吻合。

Python程式碼

# 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 isSymmetric(self, root: Optional[TreeNode]) -> bool:
        
        def dfs(subL, subR):
            if not subL and not subR:
                return True
            if not subL or not subR:
                return False
            
            return (subL.val == subR.val and
            dfs(subL.left, subR.right) and
            dfs(subL.right, subR.left))
        
        return dfs(root.left, root.right)

Leetcode 98. Validate Binary Search Tree

題目敘述：給予一個二元樹的root，去判斷這顆二元樹是否為「有效的」Binary Search Tree。

分析：所謂「有效的」指的是root的右子樹所有值都要比root的值大，並且「root的右子樹的root」，他的值一定要比「root的右子樹的root的左子樹」裡的所有值都大。所以在traverse的時候我們要傳遞原本的上限和下限。如果從root往左子樹走，我們就需要修改上限（不可比root的值大）；如果往右子樹走，我們就需要修改下限（一定要比root大）

Python程式碼

# 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 valid(node, left, right):
            if not node:
                return True
            if not (left < node.val < right):
                return False
            
            return valid(node.left, left, node.val) and valid(node.right, node.val, right)
        
        return valid(root, float('-inf'), float('inf'))

Leetcode 437. Path Sum III

有一個目標整數被視為要在一個binary tree中由相連的節點相加所得到的值。請問在一個二元樹可以找到幾條節點相加後等於目標整數的路徑。

Example:

(圖源Leetcode)

從上面的圖中我們可以看出有哪連續的節點相加後會等於8。

分析1：根據上圖，我們先觀察其中一條從root到達節點的value為1的路徑。這路徑上的值分別是：10, 5, 2, 1，現在我們要在這個路徑上尋找一個subarray相加為8。我們可以採用prefix sum的方法來找尋答案。所謂的prefix sum就是把當前的值和之前的總和相加。所以我們有了[10, 15, 17, 18]，我們可以把這些prefix sum加入到hash map中就成了{10: 1, 15: 1, 17: 1, 18:1}。每當我們有了新的prefix sum的同時也要去和我們的目標整數：8相減，並且查看當下的hash map中是否有儲存相減後的值。當我們知道18 - 8 = 10有被儲存在hash map中，我們就可以知道從有10這個subarray一路相加到18這段subarray的總和為8，這就是我們要的subarray。

另外由可能相減後等於0，所以我們需要一開始就在hash map中放入{0: 1}。

分析2：現在我們在二元樹有許多的路徑，並且根據左右子樹我們的hash map必須分開使用（不能讓不同路徑共用同一個hash map）。所以在traverse完左邊的節點後我們需要將當前的prefix sum從hash map中移掉，然後換成加入右節點相加的prefix sum。

# 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 pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        self.res = 0

        def dfs(root, prefixSums, curSum):
            if not root:
                return
            
            curSum += root.val
            self.res += prefixSums.get(curSum - targetSum, 0)
            prefixSums[curSum] = 1 + prefixSums.get(curSum, 0)
            dfs(root.left, prefixSums, curSum)
            dfs(root.right, prefixSums, curSum)
            prefixSums[curSum] -= 1
        
        dfs(root, {0 : 1}, 0)
        return self.res

後記：今天去燙頭髮，髮型師說要小心以後雄性禿。好險我還處在人生顏值的巔峰。但之後還是預防性去給醫生看一下好了。畢竟髮際線真的是男人的生命線Ｒ，而擁有判斷使用哪種演算法和將不同演算法組合起來解題的能力就是在coding interview的救命繩（會轉得太硬嗎😅