Medium
题目描述
如果一棵二叉树满足下述几个条件，则可以称为奇偶树：
- 二叉树根节点所在的层下标为 0，其子节点所在的层下标为 1，其孙节点所在的层下标为 2，依此类推。
- 偶数下标层上的所有节点的值都是奇数，从左到右按严格递增顺序排列。
- 奇数下标层上的所有节点的值都是偶数，从左到右按严格递减顺序排列。
给你二叉树的根节点，如果二叉树为奇偶树，则返回 true，否则返回 false。
示例 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 层上的节点值都是偶数且严格递减，所以这是一棵奇偶树。
示例 2：
输入：root = [5,4,2,3,3,7]
输出：false
解释：每一层的节点值分别是：
第 0 层：[5]
第 1 层：[4,2]
第 2 层：[3,3,7]
第 2 层上的节点值不满足严格递增的条件，所以这不是一棵奇偶树。
示例 3：
输入：root = [5,9,1,3,5,7]
输出：false
解释：第 1 层上的节点值应该是偶数。
提示：
- 树中节点数在范围 [1, 10^5] 内
- 1 <= Node.val <= 10^6
解题思路
这道题要求我们判断一棵二叉树是否为奇偶树。根据题目要求，我们需要按层遍历二叉树，并检查每一层的节点是否满足特定条件。
解题思路：
使用**广度优先搜索（BFS）**是最直观的解法。我们可以用队列来实现层次遍历，逐层检查节点值是否满足奇偶树的条件。
具体步骤：
- 使用队列进行BFS遍历，同时记录当前层级
- 对于每一层，将所有节点值提取到数组中
- 检查当前层是否满足条件：
- 偶数层：所有节点值为奇数且严格递增
- 奇数层：所有节点值为偶数且严格递减
- 如果任一层不满足条件，立即返回false
优化思路： 我们也可以在遍历过程中直接检查，不需要存储整层的值，这样可以节省空间。对于每个节点，我们只需要与同层的前一个节点比较即可。
这种方法的时间复杂度为O(n)，其中n是树中节点的数量，空间复杂度为O(w)，其中w是树的最大宽度。
代码实现
class Solution {
public:
bool isEvenOddTree(TreeNode* root) {
if (!root) return false;
queue<TreeNode*> q;
q.push(root);
int level = 0;
while (!q.empty()) {
int size = q.size();
int prevVal = (level % 2 == 0) ? 0 : INT_MAX;
for (int i = 0; i < size; i++) {
TreeNode* node = q.front();
q.pop();
// 检查奇偶性
if ((level % 2 == 0 && node->val % 2 == 0) ||
(level % 2 == 1 && node->val % 2 == 1)) {
return false;
}
// 检查顺序
if (level % 2 == 0) { // 偶数层，严格递增
if (node->val <= prevVal) return false;
} else { // 奇数层，严格递减
if (node->val >= prevVal) return false;
}
prevVal = node->val;
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
level++;
}
return true;
}
};
class Solution:
def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:
if not root:
return False
queue = [root]
level = 0
while queue:
next_queue = []
prev_val = 0 if level % 2 == 0 else float('inf')
for node in queue:
# 检查奇偶性
if (level % 2 == 0 and node.val % 2 == 0) or \
(level % 2 == 1 and node.val % 2 == 1):
return False
# 检查顺序
if level % 2 == 0: # 偶数层，严格递增
if node.val <= prev_val:
return False
else: # 奇数层，严格递减
if node.val >= prev_val:
return False
prev_val = node.val
if node.left:
next_queue.append(node.left)
if node.right:
next_queue.append(node.right)
queue = next_queue
level += 1
return True
public class Solution {
public bool IsEvenOddTree(TreeNode root) {
if (root == null) return false;
Queue<TreeNode> queue = new Queue<TreeNode>();
queue.Enqueue(root);
int level = 0;
while (queue.Count > 0) {
int size = queue.Count;
int prevVal = (level % 2 == 0) ? 0 : int.MaxValue;
for (int i = 0; i < size; i++) {
TreeNode node = queue.Dequeue();
// 检查奇偶性
if ((level % 2 == 0 && node.val % 2 == 0) ||
(level % 2 == 1 && node.val % 2 == 1)) {
return false;
}
// 检查顺序
if (level % 2 == 0) { // 偶数层，严格递增
if (node.val <= prevVal) return false;
} else { // 奇数层，严格递减
if (node.val >= prevVal) return false;
}
prevVal = node.val;
if (node.left != null) queue.Enqueue(node.left);
if (node.right != null) queue.Enqueue(node.right);
}
level++;
}
return true;
}
}
var isEvenOddTree = function(root) {
if (!root) return false;
let queue = [root];
let level = 0;
while (queue.length > 0) {
let size = queue.length;
let prevVal = level % 2 === 0 ? 0 : 1000001;
for (let i = 0; i < size; i++) {
let node = queue.shift();
if (level % 2 === 0) {
if (node.val % 2 === 0 || node.val <= prevVal) {
return false;
}
} else {
if (node.val % 2 === 1 || node.val >= prevVal) {
return false;
}
}
prevVal = node.val;
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
level++;
}
return true;
};
复杂度分析
| 复杂度类型 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n) | 需要遍历所有 n 个节点，每个节点访问一次 |
| 空间复杂度 | O(w) | w 是树的最大宽度，队列中最多存储一层的所有节点 |