iT邦幫忙

2021 iThome 鐵人賽

DAY 18
0
Software Development

我在刷LeetCode時邂逅了Python系列 第 18

Day 18:501. Find Mode in Binary Search Tree

今日題目

題目連結: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的範例:

https://ithelp.ithome.com.tw/upload/images/20211002/20141336y8cXNtn1Cw.png

上圖中可以看到,除了 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]

https://ithelp.ithome.com.tw/upload/images/20211002/20141336bsLt7pjcYF.png

上圖中,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


上一篇
Day 17:700. Search in a Binary Search Tree
下一篇
Day 19:1534. Count Good Triplets
系列文
我在刷LeetCode時邂逅了Python30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言