圖論應用: 奇偶二元樹 Even Odd Tree_Leetcode #1609

Leiada Krozjhen on Unsplash

題目敘述

題目會給定一棵二元樹的根結點，要求我們判定這是否為一顆合法的奇偶二元樹?

奇偶二元樹的定義:

從上到下依序是第0層、第一層、...、第n層

偶數層裡面的節點值都必須是奇數，而且由左到右嚴格遞增。

奇數層裡面的節點值都必須是偶數，而且由左到右嚴格遞減。

題目的原文敘述

測試範例

Input: root = [1,10,4,3,null,7,9,12,8,6,null,null,2]
Output: true
Explanation: The node values on each level are:
Level 0: [1]
Level 1: [10,4]
Level 2: [3,7,9]
Level 3: [12,8,6,2]
Since levels 0 and 2 are all odd and increasing and levels 1 and 3 are all even and decreasing, the tree is Even-Odd.

Example 2:

Input: root = [5,4,2,3,3,7]
Output: false
Explanation: The node values on each level are:
Level 0: [5]
Level 1: [4,2]
Level 2: [3,3,7]
Node values in level 2 must be in strictly increasing order, so the tree is not Even-Odd.

Example 3:

Input: root = [5,9,1,3,5,7]
Output: false
Explanation: Node values in the level 1 should be even integers.

約束條件

Constraints:

• The number of nodes in the tree is in the range [1, 10^5].

節點總數量介於1~十萬之間。

• 1 <= Node.val <= 10^6

每個節點值的範圍落在1~一百萬之間。

演算法 BFS (Level-order traversal)

由奇偶二元樹的定義可以知道，規則是依賴當下層數的奇偶來決定。

因此，最適合的選擇就是BFS廣度優先搜索，先天具有逐層由上到下拜訪的特質。

並且在每一層拜訪的時候，加上對應的偶數、奇數判斷，和遞增、遞減判斷即可。

奇偶二元樹的定義:

從上到下依序是第0層、第一層、...、第n層

偶數層裡面的節點值都必須是奇數，而且由左到右嚴格遞增。

奇數層裡面的節點值都必須是偶數，而且由左到右嚴格遞減。

程式碼 BFS (Level-order traversal)

class Solution:
    def isEvenOddTree(self, root: TreeNode) -> bool:
        
        queue = [(root)] if root else []
        
        is_odd = lambda x: (x % 2 == 1)
        is_even = lambda x: (x % 2 == 0)
        
        level = 0
        
        while queue:
            
            next_queue = []
            prev_value = None
            
            even_level = True if is_even(level) else False
            
            for idx, node in enumerate(queue):
            
                # check for value of even/odd property
                if even_level and not is_odd(node.val):
                    return False
                
                if not even_level and not is_even(node.val):
                    return False
                
                # check for monotone increasing/decreasing
                if idx == 0:
                    # left-most node
                    prev_value = float('-inf') if is_even(level) else float('inf')
                
                else:
                    # non left-most node
                    
                    if is_even(level) and prev_value >= node.val:
                        return False

                    elif is_odd(level) and prev_value <= node.val:
                        return False
                
                # update current node value as previous value
                prev_value = node.val
                
                # append children node if they exist
                if node.left:
                    next_queue.append(node.left)
                
                if node.right:
                    next_queue.append(node.right)
            
            # update queue and level for next level traversal
            queue = next_queue
            level += 1
            
        return True
                

複雜度分析

時間複雜度:

BFS廣度優先拜訪整棵樹，每個節點至多拜訪一次。所需時間為O(n)

空間複雜度:

BFS quque所需成本為O(n)，最大成本落在最後一層。

關鍵知識點

由奇偶二元樹的定義可以知道，規則是依賴當下層數的奇偶來決定。

因此，最適合的選擇就是BFS廣度優先搜索，先天具有逐層由上到下拜訪的特質。

Reference:

[1] Even Odd Tree - LeetCode