LeetCode第 209 场周赛 5532.奇偶树

题目：5532.奇偶树

Description

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

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

给你二叉树的根节点，如果二叉树为 奇偶树 ，则返回 true ，否则返回 false 。

Sample

示例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 层上的节点值不满足严格递增的条件，所以这不是一棵奇偶树。

PS

树中节点数在范围 [1, 10⁵] 内 1 <= Node.val <= 10⁶

Solution

二叉树的层序遍历！维护一个队列！根据条件判断是否满足条件！

AC Code

class Solution { public: bool isEvenOddTree(TreeNode* root) { if(root==NULL) return true; int level=0;//当前层数 int now=0; int next=0; int base=0;//当前数字需比较的上一个数字 queue<TreeNode*> q; q.push(root); now++; base=root->val-1; while(!q.empty()){ TreeNode * temp = q.front(); if(temp->val%2==level%2) return false;//层数与该层内的节点的值奇偶性相同 if(level%2 && temp->val >= base) return false;//奇数层非递减 if(level%2==0 && temp->val <= base) return false;//偶数层非递增 q.pop(); now--; base=temp->val; if(temp->left) { q.push(temp->left); next++; } if(temp->right) { q.push(temp->right); next++; } if(now==0){ now=next; next=0; level++; if(!q.empty()) { base=q.front()->val; if(level%2) base++; else base--; } } } return true; } };