题目大意：
奇偶树
如果一棵二叉树满足下述几个条件，则可以称为 奇偶树 ：
- 二叉树根节点所在层下标为 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 层上的节点值应为偶数。
示例 4：
输入：root = [1] 输出：true
示例 5：
输入：root = [11,8,6,1,3,9,11,30,20,18,16,12,10,4,2,17] 输出：true
提示：
- 树中节点数在范围
[1, 105]内 1 <= Node.val <= 106
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1609
解题思路分析：
本题题意很清晰，我们要对二叉树每一层上的节点进行顺序扫描。偶数行必须都是奇数并从左至右升序排列，奇数行都是偶数并从左至右降序排列。逐层扫描二叉树最好的方式就是bfs广度优先搜索！
bfs解题时，我们定义一个层数变量，起始为0。逐层扫描时，我们再使用一个变量来记录当前层前一位置上的节点值，当前为偶数层时，如果当前节点值是偶数或者大于等于前节点，直接返回false。反之当前位奇数层时，如果当前节点值是奇数或者小于等于前节点，也直接返回false。当bfs扫描完所有节点后，证明该二叉树为合理奇偶树，返回true。
实现代码：
public boolean isEvenOddTree(TreeNode root) {
Queue<TreeNode> q = new LinkedList<>(); // bfs使用的Queue
q.offer(root); // 将根节点作为bfs起始点，加入到Queue中
int level=0; // 初始层数
while(q.size()>0){ // 开始bfs
int size=q.size(); // 当前Queue中存在元素个数即是当前层的元素个数
// 前一节点值。（默认情况下，奇数行是Int最大值，偶数行是0）
int preNum=level%2==0?0:Integer.MAX_VALUE;
while(size>0){ // 循环当前行的每一个节点
TreeNode node=q.poll(); // 从Queue中取出一个节点
size--; // 当前行元素个数减一
if(level%2==0){ // 如果是偶数行
if(node.val%2==0) return false; // 当前元素是偶数，返回false
if(node.val<=preNum) return false; // 当前元素小于等于前元素，返回false
}else{ // 如果是奇数行
if(node.val%2!=0) return false; // 当前元素是奇数，返回false
if(node.val>=preNum) return false; // 当前元素大于等于前元素，返回false
}
preNum=node.val; // 使用当前元素更新前元素
if(node.left!=null) q.offer(node.left); // 将左子节点加入到Queue
if(node.right!=null) q.offer(node.right); // 将右子节点加入到Queue
} // 当前层遍历结束
level++; // 层数加一
}
return true;
} 本题解法执行时间为8ms。
Runtime: 8 ms, faster than 99.31% of Java online submissions for Even Odd Tree.
Memory Usage: 56.1 MB, less than 85.82% of Java online submissions for Even Odd Tree.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1609-even-odd-tree-解题思路分析/