前往
大廳
主題

LeetCode - 1609. Even Odd Tree 解題心得

Not In My Back Yard | 2024-05-14 12:00:17 | 巴幣 0 | 人氣 37

題目連結:


題目意譯:
一棵二元樹如果滿足以下條件,則會被稱作是 Even-Odd:
    該二元樹的根節點位於階層索引值 0,其小孩位於階層索引值 1,而他們的小孩位於階層索引值 2,以此類推。
    對於每一個偶數索引值階層,位於該階層的節點都有著奇數數值,且從左至右按照嚴格遞增排序。
    對於每一個奇數索引值階層,位於該階層的節點都有著偶數數值,且從左至右按照嚴格遞減排序。

給定一棵二元樹的根節點 root。如果該樹為 Even-Odd,則回傳真(True);反之,回傳假(False)。

限制:
樹中的節點數位於範圍 [1, 10 ^ 5] 中。
1 ≦ Node.val ≦ 10 ^ 6

-
範例測資:
範例 1:
輸入: root = [1,10,4,3,null,7,9,12,8,6,null,null,2]
輸出: true
解釋: 每一階層的節點值為:
階層 0: [1]
階層 1: [10,4]
階層 2: [3,7,9]
階層 3: [12,8,6,2]
由於階層 0 和 2 的數字都是奇數且遞增,而階層 1 和 3 的數字都是偶數且遞減。因此該樹為 Even-Odd。

範例 2:
輸入: root = [5,4,2,3,3,7]
輸出: false
解釋: 每一階層的節點值為:
階層 0: [5]
階層 1: [4,2]
階層 2: [3,3,7]
階層 2 的數字必須是嚴格遞增之順,因此該樹不是 Even-Odd。

範例 3:
輸入: root = [5,9,1,3,5,7]
輸出: false
解釋: 階層 1 的數字必須是偶數。


解題思維:
一樣沒什麼能說的。就是階層探訪(Level-Order Traversal)的變體。參見這題。只要檢查每個偶數層是不是只包含奇數且嚴格遞增,然後檢查奇數層是不是只包含偶數且嚴格遞減(即如題目敘述)即可。




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

創作回應

更多創作