力扣 1609. 奇偶树

最新推荐文章于 2025-06-05 14:05:55 发布

原创最新推荐文章于 2025-06-05 14:05:55 发布

· 206 阅读

0 ·

版权

文章标签：

#leetcode #算法

BFS 专栏收录该内容

13 篇文章

订阅专栏

本文解析了LeetCode上的题目，介绍了如何通过广度优先搜索(BFS)算法判断给定的二叉树是否满足奇数层节点值为偶数且递减、偶数层节点值为奇数且递增的规则。代码展示了如何遍历并验证每个节点值遵循的规律。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目来源：https://leetcode-cn.com/problems/even-odd-tree/

大致题意：
给一个二叉树，检查二叉树是否满足以下规则：

设根节点层数为 0，子节点的层数为父节点层数 + 1
奇数层的节点值都为偶数，且从左到右严格递减
偶数层的节点值都为奇数，且从左到右严格递增

思路

需要一层一层的判断，那么就需要广度优先遍历

BFS

初始化层数为 0，使用队列存下要遍历的节点，初始时放入根节点
开始循环，每轮循环开始时统计此时的队列大小，也就是本层的节点数量，然后按照当前层的规则遍历取出节点，判断是否符合规则，并且遍历时存下当前节点的子节点
每一轮循环结束后层数 +1

代码：

public boolean isEvenOddTree(TreeNode root) {
        Queue<TreeNode> queue = new ArrayDeque<>();
        // 记录层数
        int level = 0;
        queue.offer(root);
        while (!queue.isEmpty()) {
            // 当前层的节点个数
            int size = queue.size();
            // 奇数层递减，因而初始值设为最大边界值 + 1
            // 偶数层递增，因而初始值设为最小边界值 - 1
            int preVal = level % 2 == 0 ? 0 : 1000001;
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                int val = node.val;
                // 层数为偶数，值应该为奇数；层为奇数，值应该为偶数
                // 因而它们对 2 取余的结果应该总是不相同的
                if (level % 2 == val % 2) {
                    return false;
                }
                // 偶数层应该递增，奇数层应该递减
                if ((level % 2 == 0 && val <= preVal) || (level % 2 == 1 && val >= preVal)) {
                    return false;
                }
                // 存下子节点入队列
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
                // 更新左侧节点的值
                preVal = val;
            }
            level++;
        }
        return true;
    }