67 BFS解奇偶树

问题描述：如果一个二叉树满足下述几个条件，则可以称为奇偶树：二叉树根节点所在层下标为0，根的子节点所在层下标为1，根的孙节点所在蹭的下标为2，依次类推，偶数下标层上的所有节点的值都是奇整数，从左到右按顺序严格递增。奇数下标蹭上的所有节点值都是偶整数，从左到右的顺序递减，给你二叉树的根节点，如果二叉树为奇偶树，则返回true，否则返回false，

bfs求解：由于需要一层一层的判断，所以采用bfs进行求解具有方便性，首先定义一个队列，首先判断根节点是否满足要求，若满足要求则放入队列中，然后在while循环中将所有的元素都拿出来一一对比，若满足要求则继续放入队列中，否则返回false；

//首先定义bfs函数，输入为根节点，输出为Boolean
public Boolean bfs(TreeNode root)
{
//首先定义一个队列用来进行bfs遍历
Queue<TreeNode>queue=new LinkedList<TreeNode>();
//首先将根节点放入其中
queue.add(root)
//每次while循环index+1,并用index%2表征该层应该为偶数还是奇数，例如第一层root需要为奇数
//则判断root.val%1==index%1,如果不成立，则返回false，否则进行下一种判断。
int index=1;
while(!queue.isEmpty())
{
//首先需要进行两种队列中元素的个数判断，若只有一个则不需要进行顺序和逆序排列
//该判断如果队列中只有一个元素的情景
if(queue.size()==1)
{
//首先弹出这个元素
TreeNode tn=queue.poll();
//如果这个元素值不满足要求，则返回false
if(TreeNode.val%2!=idnex%2)
{
return false;
//
}else
{
//若满足要求则将其子元素放入队列之中
queue.add(tn.left);
queue.add(tn.right);
}
}
//该else即为判断结果表示有多个元素
else
{
//首先记录元素的个数
int quesize=queue.size();
//将第一个元素弹出来作为第一个元素
TreeNode lastNode=queue.poll();
//该元素需要进行值的判断
if(lastNode.val%2!=idnex%2)
{
return false;
}else
{
queue.add(tn.left);
queue.add(tn.right);
}
//接下来按照层级进行顺序判断，若层级为偶数层，则从左往右递增
//该层级表示递增
if(index%2==1)
{
for(int i=1;i<quesize;i++)
{
TreeNode next=queue.poll();
//每一个元素首先进行值的判断
if(lastNode.val%2!=idnex%2)
{
return false;
}else
{
//值的奇偶性判断成功后进行递增判断，如果成功则添加子节点，并更新lastNode
if(next.val<lastNode.val){return false;}else
{
queue.add(next.left);
queue.add(next.right);
lastNode=next;
}
}

}
该层级表示递减
}else
{
for(int i=1;i<quesize;i++)
{
TreeNode next=queue.poll();
if(lastNode.val%2!=idnex%2)
{
return false;
}else
{
if(next.val<lastNode.val){return false;}else
{
queue.add(next.left);
queue.add(next.right);
lastNode=next;
}
}

}
}
}
//最后index+1
index+=1;
}
return true;
}