前往
大廳
主題

LeetCode - 872. Leaf-Similar Trees 解題心得

Not In My Back Yard | 2021-01-31 00:00:05 | 巴幣 0 | 人氣 230

題目連結:


題目意譯:
考慮一個二元樹的所有葉節點,按照從左到右的順序,所有葉節點的值形成一個葉序列。

例如上圖給定的樹,葉序列為 (6, 7, 4, 9, 8)。

兩個二元樹被視作葉相似,如果兩者的葉序列是相同的。

回傳真(True)若且唯若兩個給定的樹,其根節點分別為 root1 和 root2,為葉相似的。

限制:
每棵樹的節點數位於範圍 [1, 200]。
兩棵樹的節點之值皆位於範圍 [0, 200]。



範例測資:
範例 1:
輸入: root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
輸出: true

範例 2:
輸入: root1 = [1], root2 = [1]
輸出: true

範例 3:
輸入: root1 = [1], root2 = [2]
輸出: false

範例 4:
輸入: root1 = [1,2], root2 = [2,2]
輸出: true

範例 5:
輸入: root1 = [1,2,3], root2 = [1,3,2]
輸出: false


解題思維:
採用深度優先搜尋(Depth First Search)將所有葉節點找出來,作法有點像這題

兩棵樹的葉節點都找出來各形成一個序列後,比較兩者的序列即可。一樣就為真,不一樣就為假。




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

創作回應

更多創作