[数据结构与算法]奇偶树：二叉树的层次遍历

题目描述

考查：二叉树的层次遍历

package year2021.month12.day25;

import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.Queue;

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 LinkedList<>();
		queue.offer(root);
		boolean even = true;// 是否偶数层
		while (!queue.isEmpty()) {
			int size = queue.size();
			int prev = even ? Integer.MIN_VALUE : Integer.MAX_VALUE;
			while (size-- > 0) {
				TreeNode top = queue.poll();
				int est = top.val;
				if (even) {// 偶数下标都为奇数且严格递增
					if (est % 2 == 0 || prev >= est)
						return false;
				} else {// 奇数下标都为偶数且严格递减
					if (est % 2 != 0 || prev <= est)
						return false;
				}
				prev = est;
				if (top.left != null)
					// 将此节点的左子树根节点入队列
					queue.offer(top.left);
				if (top.right != null)
					// 将此节点的右子树根节点入队列
					queue.offer(top.right);
			}
			even = !even;
		}
		return true;
	}
}