奇偶樹
- 1609.奇偶樹
- 題目描述
- 思路
- BFS
- Python實作
- Java實作
1609.奇偶樹
題目描述
奇偶樹
思路
BFS
由于判斷一棵二叉樹是否為奇偶樹的條件是針對同一層的節點，因此可以使用BFS，每一輪搜索訪問同一層的全部節點，且只會訪問這一層的節點，
使用佇列存盤節點，初始時，將根節點加入佇列，每一輪搜索之前，佇列中的節點是同一層的全部節點，記佇列的大小為size，該輪搜索只訪問size個節點，即可保證該輪搜索訪問的恰好是同一層的全部節點，搜索程序中，將當前層的節點的非空子節點依次加入佇列，用于下一層的搜索，
判斷一棵二叉樹是否為奇偶樹，需要考慮兩個條件，一是節點值的奇偶性，二是節點值的單調性，這兩個條件都由層下標的奇偶性決定，因此，需要維護搜索到的層下標，以及對于每一層搜索都需要維護上一個節點值，
如果當前層下標是偶數，則要求當前層的所有節點的值都是奇數，且節點值從左到右嚴格遞增，如果遇到節點值是偶數，或者當前節點值小于等于上一個節點值，則二叉樹一定不是奇偶樹，
如果當前層下標是奇數，則要求當前層的所有節點的值都是偶數，且節點值從左到右嚴格遞減，如果遇到節點值是奇數，或者當前結點值大于等于上一個節點值，則二叉樹一定不是奇偶樹，
如果二叉樹的所有節點都滿足奇偶樹的條件，則二叉樹是奇偶樹，
Python實作
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:
queue = [root]
level = 0
while queue:
prev = float('inf') if level % 2 else 0
nxt = []
for node in queue:
val = node.val
if val % 2 == level % 2 or level % 2 == 0 and val <= prev or level % 2 == 1 and val >= prev:
return False
prev = val
if node.left:
nxt.append(node.left)
if node.right:
nxt.append(node.right)
queue = nxt
level += 1
return True
Java實作
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isEvenOddTree(TreeNode root) {
Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
queue.offer(root);
int level = 0;
while (!queue.isEmpty()) {
int size = queue.size();
int prev = level % 2 == 0 ? Integer.MIN_VALUE : Integer.MAX_VALUE;
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
int value = node.val;
if (level % 2 == value % 2) {
return false;
}
if ((level % 2 == 0 && value <= prev) || (level % 2 == 1 && value >= prev)) {
return false;
}
prev = value;
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
level++;
}
return true;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/395433.html
標籤：其他