Sponsored
Sponsored
This approach employs a breadth-first search (BFS) to traverse the binary tree level by level. We maintain a queue to keep track of the nodes at each level, examining their values to ensure compliance with the Even-Odd criteria:
Time Complexity: O(N), where N is the number of nodes, as each node is inspected once.
Space Complexity: O(M), where M is the maximum number of nodes at any level in the tree (width of the tree), due to the BFS queue.
1from collections import deque
2
3class TreeNode:
4 def __init__(self, val=0, left=None, right=None):
5 self.val = val
6 self.left = left
7 self.right = right
8
9class Solution:
10 def isEvenOddTree(self, root: TreeNode) -> bool:
11 if not root:
12 return False
13
14 queue = deque([root])
15 level = 0
16
17 while queue:
18 level_length = len(queue)
19 prev = None
20
21 for _ in range(level_length):
22 node = queue.popleft()
23
24 # Check current node value with constraints
25 if level % 2 == 0:
26 if node.val % 2 == 0 or (prev is not None and node.val <= prev):
27 return False
28 else:
29 if node.val % 2 != 0 or (prev is not None and node.val >= prev):
30 return False
31
32 prev = node.val
33
34 if node.left:
35 queue.append(node.left)
36 if node.right:
37 queue.append(node.right)
38
39 level += 1
40
41 return TrueThe solution employs a queue for level-order traversal. On each level, it examines the nodes' values to ensure conformity with the problem's even-odd level requirements.
This approach applies a depth-first search (DFS) method, maintaining level information to confirm constraints. We use recursion to explore the tree, while an array stores the last value seen on each level to validate order constraints.
Time Complexity: O(N), with N being the number of nodes.
Space Complexity: O(H), where H is the height of the tree, accounting for recursion stack and the array storing last values at each level.
1#include <vector>
2#include <algorithm>
3using namespace std;
4
5struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
bool isValid(TreeNode* node, int level, vector<int>& lastVals) {
if (!node) return true;
if (lastVals.size() <= level) {
lastVals.push_back(level % 2 == 0 ? INT_MIN : INT_MAX);
}
if ((level % 2 == 0 && (node->val % 2 == 0 || node->val <= lastVals[level])) ||
(level % 2 == 1 && (node->val % 2 == 1 || node->val >= lastVals[level]))) {
return false;
}
lastVals[level] = node->val;
return isValid(node->left, level + 1, lastVals) && isValid(node->right, level + 1, lastVals);
}
bool isEvenOddTree(TreeNode* root) {
vector<int> lastVals;
return isValid(root, 0, lastVals);
}
};In the C++ solution, we use a recursive function to perform DFS while maintaining the last meaningful value for level validation in an array. This array ensures all nodes at each level meet the Even-Odd Tree constraints.