612，BFS和DFS解奇偶树
问题描述
来源：LeetCode第1609题
难度：中等
如果一棵二叉树满足下述几个条件，则可以称为奇偶树：
二叉树根节点所在层下标为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
BFS解决
看到这道题的条件我们最容易想到的就是BFS解决，也就是一层一层的遍历。遍历每一层的时候我们只需要满足以下两个条件即可：
偶数层的节点值都是奇数并且从左到右递增
奇数层的节点值都是偶数并且从左到右递减
只要有一个不满足，就返回false。对于二叉树的BFS遍历我们前面已经介绍过很多次了，如下图所示
他的代码我们再来看下
public void BFS(TreeNode node) {
//使用一个队列
Queue<TreeNode> queue = new LinkedList<>();
queue.add(node);
while (!queue.isEmpty()) {
//出队
TreeNode curNode = queue.poll();
//访问当前节点
System.out.println(curNode.val);
//左右子节点只要有一个不为空就把他加入到队列中
if (curNode.left != null)
queue.add(curNode.left);
if (curNode.right != null)
queue.add(curNode.right);
}
}
我们只需要参照上面的代码修改一下就是这题的答案。
public boolean isEvenOddTree(TreeNode root) {
Queue<TreeNode> queue = new LinkedList();
//把根节点加入到队列中
queue.add(root);
boolean even = true;//默认根节点是偶数层
while (!queue.isEmpty()) {
//每一层节点的个数
int levelCount = queue.size();
//每层节点的前一个节点值
int prevVal = even ? Integer.MIN_VALUE : Integer.MAX_VALUE;
//遍历当前层的所有节点
while (levelCount-- > 0) {
TreeNode curNode = queue.poll();
//偶数层上的节点都是奇数，并且是递增的，如果不满足条件直接返回false
if (even && (curNode.val % 2 == 0 || curNode.val <= prevVal))
return false;
//奇数层上的节点都是偶数，并且是递减的
if (!even && (curNode.val % 2 == 1 || curNode.val >= prevVal))
return false;
//更新前一个节点
prevVal = curNode.val;
//如果左右子节点不为空，就把他加入到队列中
if (curNode.left != null)
queue.add(curNode.left);
if (curNode.right != null)
queue.add(curNode.right);
}
//奇偶交换
even = !even;
}
return true;
}
DFS解决
这题除了BFS我们还可以使用DFS来解决，这里使用的DFS就是二叉树的前序遍历。我们可以参照609，从先序遍历还原二叉树的最后一种解法。使用一个list集合存储每层的节点，注意，每层只存储一个节点。
当前节点所在的层数如果是第一次访问，我们就把他加入到集合list中。否则就需要和他前面的值进行比较。究竟是递增还是递减，这个需要根据所在是层数来决定的。代码如下
public boolean isEvenOddTree(TreeNode root) {
//list集合，每层只存储一个节点
List<Integer> mList = new ArrayList<>();
return dfs(root, mList, 0);
}
//level表示访问的当前节点是在第几层
private boolean dfs(TreeNode root, List<Integer> mList, int level) {
if (root == null)
return true;
//偶数层的值都是奇数，奇数层的值都是偶数，如果不满足直接返回false
if (root.val % 2 == level % 2)
return false;
//这里是判断当前层是不是第一次遍历，也可以这样理解，就是当前节点
//是不是这一层的第一个节点，如果不是第一个节点，我们需要和前面的
//比较，如果是第一个节点，就没法和前面一个节点比较，直接存储到
//集合list中。
if (mList.size() > level) {
//根据当前节点是奇数层还是偶数层，来判断是递增还是递减
if ((level % 2 == 1 && mList.get(level) <= root.val) ||
((level % 2 == 0) && mList.get(level) >= root.val))
return false;
mList.set(level, root.val);
} else {
mList.add(root.val);
}
//继续访问他的左右两个子节点
return dfs(root.left, mList, level + 1)
&& dfs(root.right, mList, level + 1);
}
截止到目前我已经写了600多道算法题了，为了方便大家阅读，我把部分算法题整理成了pdf文档，目前有1000多页，大家可以在下面公众号“数据结构和算法”中回复关键字“pdf”即可获取下载链接。