今日題目

題目連結：501. Find Mode in Binary Search Tree
題目主題：Tree, Depth-First Search, Binary Search Tree, Binary Tree

今天的主題雖然放在Binary Search Tree，但題目的實作上其實也是在複習Depth-First Search。

簡單說說 Binary Search Tree With Duplicates

在前面文章中提過Binary Search Tree的其中一個原則是不會有節點出現重複的值，但有時候會有例外，例如本題就提到，這是一個會有重複節點的Binary Search Tree，下圖是一個Binary Search Tree With Duplicates的範例：

上圖中可以看到，除了 9 有出現重複以外，其他條件都還是符合 Binary Search Tree 的原則。

題目解說

建議可以看看LeetCode原本的題目說明，這邊是用我的方式說明題目，參考就好。

題目會給一顆 Binary Search Tree With Duplicates，目的是在這棵樹中找出重複最多次的值，最終要回傳這棵樹出現最多次的值，若有兩個以上值同樣是出現最多次的，需要全部都回傳。

約束：

• 樹的節點總數範圍在[1, 10的4次方]
• -10的5次方 <= Node.val <= 10的5次方

範例1

輸入：root = [1,null,2,2]
輸出：[2]

範例2

輸入：root = [0]
輸出：[0]

建議到這邊先停下來，嘗試自己解解看，若沒有想法可再繼續走下去。

解題的想像

文字描述

1. 寫一個遞迴方法，傳入要前往的節點及一個map
2. 遞迴方法會用Preorder Traversal的方式走完整棵樹，並且最後回傳一個完整的map。map會記錄每個值出現的次數。
3. 確認map被記錄到最多次數的數字
4. 回傳所有出現最多次數的值

圖解過程

範例：root = [1, -10, 9, -10, -3, 9, 13]

上圖中，step1 ~ step7 是用Preorder的方式走的過程，可以看到每一輪都會把現在的值放進map看目前這個值有幾個，map中的方框資料左邊為 key 是目前的值、右邊為 value 是這個值現在出現過幾次的數字。

可以特別看看 step5 ～ step6 的過程，在 step5 時因為 map 中還沒有 9 這個值出現，因此放一個 9 進去這個 map，到 step6 可以看到 因為 map 中已經有 9 了，所以直接把 9 的出現次數 +1。

最後整棵樹走過一次以後，看到 step8 ~ step9，在step8 用map可以看到 -10 跟 9 都出現過兩次，沒有比他們的出現次數還要更多的值了，step9 就是最後要輸出的結果。

若因為沒想法而走到這邊，建議看完想像以後再給自己一次機會試一次。

程式碼撰寫

class Solution:
    def traversal(self, node: Optional[TreeNode], map):
        if node == None: return map
        # 如果有節點，將值放進map中
        if node.val in map:
            map[node.val] += 1
        else:
            map[node.val] = 1
        # 繼續往左邊節點去確認值
        map = self.traversal(node.left, map)
        # 繼續往右邊節點去確認值
        map = self.traversal(node.right, map)
        
        return map
        
    def findMode(self, root: Optional[TreeNode]) -> List[int]:
        map = self.traversal(root, {})
        # 確認最多出現次數的數字
        maxValue = max(map.values())
        # 從map把所有出現次數最多的值都回傳
        return [key for key in map.keys() if map[key] == maxValue]

希望您今天能瞭解到...

1. Binary Search Tree With Duplicates
2. 501. Find Mode in Binary Search Tree的解題方法

若內容有什麼問題或建議歡迎一起交流：）
感謝您今天願意花時間看完這篇文章~~~~

Next：1534. Count Good Triplets