切換
舊版
前往
大廳
主題

LeetCode - 112. Path Sum 解題心得

Not In My Back Yard | 2020-08-19 00:26:25 | 巴幣 0 | 人氣 199

題目連結:


題目意譯:
給定一棵二元樹以及一個和 sum,判斷給定的樹是否有一個從根節點到葉節點的路徑其經過的節點之值總和恰為 sum。

注:葉節點為沒有子節點的節點。



範例測資:
給定下列二元樹以及 sum = 22,
      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1
回傳真(true),因存在一根節點到葉節點的路徑 5 → 4 → 11 → 2 ,其總和為 22 。



解題思維:
就是單純以深度優先搜尋(Depth First Search,DFS)窮舉出所有路徑,並且求出該路徑上的所有節點之和然後跟 sum 之值比對。如果有任何一條路徑和等於 sum ,則回傳真(true);反之回傳假(false)。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作