MediumRating 1749

1609. Even Odd Tree

treebfsbinary-tree

解題說明

Even Odd Tree

題目描述：給定一棵二元樹，若它滿足「奇偶樹」條件則回傳 true，否則回傳 false。偶數層（0, 2, 4, …）的節點值必須全為奇數，且從左到右嚴格遞增；奇數層（1, 3, 5, …）的節點值必須全為偶數，且從左到右嚴格遞減。

解題思路：使用 BFS 逐層遍歷。對每一層，記錄層號的奇偶性，然後逐一檢查每個節點：值的奇偶是否符合、相鄰節點的大小順序是否正確（用前一個節點值 prev 做比較）。任一條件不符即回傳 false，全部通過則回傳 true。

C++ 解法

複雜度分析

時間複雜度：O(n) — 每個節點恰好被訪問一次。

空間複雜度：O(w) — w 為樹的最大寬度，BFS 佇列最多同時存放一層節點；最壞為 O(n/2) = O(n)（完全二元樹的最後一層）。

虛擬碼

1. Push root into queue; level = 0
2. While queue is not empty:
   a. sz = queue size; set prev = INT_MIN (even level) or INT_MAX (odd level)
   b. For each of the sz nodes:
      - Dequeue node, get val
      - If even level: fail if val is even OR val <= prev
      - If odd level:  fail if val is odd  OR val >= prev
      - Update prev = val
      - Enqueue left and right children if they exist
   c. level++
3. Return true

其他解法

DFS 遞迴 O(n)：DFS 時傳入當前層號及上一個同層節點值（可用 unordered_map<int, int> prevAtLevel 儲存）。每次訪問節點時查詢並更新 prevAtLevel[level]，同樣逐節點驗證。邏輯與 BFS 相同，但需額外空間存各層前驅值，且遞迴棧深度為樹高 O(h)。

逐層收集再驗證 O(n)：先用 BFS 或 DFS 把每層節點值存入 vector<vector<int>>，再對每層做奇偶與單調性檢查。程式碼更直觀但需額外 O(n) 儲存所有節點值。

延伸思考

如果樹非常深（退化成鏈結串列），DFS 遞迴是否會有堆疊溢位風險？如何改寫為迭代版本？
若題目改為「每層節點值必須嚴格遞增，不論奇偶」，程式碼需要做哪些修改？
如何設計一個函式，自動生成一棵滿足奇偶樹條件的隨機二元樹用於測試？

解題說明

Even Odd Tree

虛擬碼

1. Push root into queue; level = 0 2. While queue is not empty: a. sz = queue size; set prev = INT_MIN (even level) or INT_MAX (odd level) b. For each of the sz nodes: - Dequeue node, get val - If even level: fail if val is even OR val <= prev - If odd level: fail if val is odd OR val >= prev - Update prev = val - Enqueue left and right children if they exist c. level++ 3. Return true

其他解法

延伸思考

如果樹非常深（退化成鏈結串列），DFS 遞迴是否會有堆疊溢位風險？如何改寫為迭代版本？
若題目改為「每層節點值必須嚴格遞增，不論奇偶」，程式碼需要做哪些修改？
如何設計一個函式，自動生成一棵滿足奇偶樹條件的隨機二元樹用於測試？