612，BFS和DFS解奇偶树

Original 博哥数据结构和算法 2022-05-01

问题描述

来源：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);
}