付費限定文章

圖論應用題: 判定是否為葉子相似樹? Leaf-similar Trees_Leetcode #871_精選75題

Annie Spratt on Unsplash

題目敘述

題目會給定兩顆二元樹的根結點，要求我們判斷這兩顆二元樹是否為 葉子相似樹?

葉子相似樹的定義

兩顆二元樹，從左到右看的葉子結點的序列完全相同。

例如下圖中的這兩顆二元樹，從左到右看的葉子結點的序列 = [6, 7, 4, 9, 8] 完全相同。

題目的原文敘述

測試範例

Example 1:

Input: 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]
Output: true

從左到右看的葉子結點的序列 = [6, 7, 4, 9, 8] 完全相同。

Example 2:

Input: root1 = [1,2,3], root2 = [1,3,2]
Output: false

第一顆樹，從左到右看的葉子結點的序列 = [2, 3] 
第二顆樹，從左到右看的葉子結點的序列 = [3, 2]
不同，返回False​

約束條件

Constraints:

• The number of nodes in each tree will be in the range [1, 200].

一顆二元樹的結點總數目介於1~200之間。

• Both of the given trees will have values in the range [0, 200].

節點值都會介於0~200之間。

演算法

這題的破題關鍵在於「葉子結點」，而且題目又給了葉子相似樹的定義

葉子相似樹的定義

兩顆二元樹，從左到右看的葉子結點的序列完全相同。

那麼，我們只要順著題目的規定，拜訪整顆樹，依照從左到右的順序，列出每個葉子結點的值，並且比較是否完全相同即可。