奇偶树 | 徐年の博客

力扣 1609. 奇偶树

题目说明

如果一棵二叉树满足下述几个条件，则可以称为奇偶树：

二叉树根节点所在层下标为 0 ，根的子节点所在层下标为 1 ，根的孙节点所在层下标为 2 ，依此类推。
偶数下标层上的所有节点的值都是奇整数，从左到右按顺序严格递增
奇数下标层上的所有节点的值都是偶整数，从左到右按顺序严格递减
给你二叉树的根节点，如果二叉树为奇偶树，则返回 true ，否则返回 false 。

提示：

树中节点数在范围 [1, 10^5] 内
1 <= Node.val <= 10^6

示例

示例 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:

1
2
3

输入：root = [5,9,1,3,5,7]
输出：false
解释：1 层上的节点值应为偶数。

示例 4:

1 2	输入：root = [1] 输出：true

示例 5:

1 2	输入：root = [11,8,6,1,3,9,11,30,20,18,16,12,10,4,2,17] 输出：true

笔者理解

此题是一道二叉树算法问题，在力扣题库中被定义为中等题。

解法

当笔者阅读完此题后，发现此题中我们直接层序遍历如何判断每层即可，不过读者切记需要判断是否“严格”递增，让我们来看看具体如何实现的吧。

实现

/**
 * Definition for a binary tree node.
 * public 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) {
        // 根节点非奇节点
        if ((root.val & 1) == 0) {
            return false;
        }

        Deque<TreeNode> stack = new LinkedList<>();

        if (root.left != null) {
            stack.offer(root.left);
        }
        if (root.right != null) {
            stack.offer(root.right);
        }

        int tick = 0;

        while (!stack.isEmpty()) {
            int size = stack.size();

            int last = -1; 

            for (int i = 0; i < size; i++) {
                TreeNode node = stack.pop();

                if (node.left != null) {
                    stack.offer(node.left);
                }
                if (node.right != null) {
                    stack.offer(node.right);
                }

                int num = node.val;

                // 奇偶性错误
                if ((num & 1) != tick) {
                    return false;
                }

                // 首元素
                if (last == -1) {
                    last = num;
                    continue;
                }

                // 和上一个数相等代表非严格递增或者递减
                if (num == last) {
                    return false;
                }

                // 增减性错误
                int count = num > last? 1: 0;
                if (count != tick) {
                    return false;
                }

                last = num;
            }

            tick = (tick + 1) & 1;
        }

        return true;
    }
}