5532. 奇偶树

题目描述：

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

二叉树根节点所在层下标为 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

提示：

树中节点数在范围 [1, 100000] 内 1 <= Node.val <= 1000000

解题思路：

首先想到的是层次遍历（切分每一层节点）；

1）、分析奇偶树的成立条件，删选出不符合的条件； 首先是偶数行的数据必须为奇数，奇数行的数据必须为偶数： (node->val & 1) == true 则可以知道是奇数，反之为偶数； 偶数行是从小到大，奇数行是从大到小；（严格递增以及严格递减）： 难点：判断每层的第一个节点的val值；以此与前一个节点的val比较；

2）、三个不成立的条件：

if ((cur & 1) != zt) return false ; if (cur == precur) return false; if ((cur > precur) != zt) return false ;

代码实现：

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: bool isEvenOddTree(TreeNode* root) { TreeNode* pre = root , *nextN = NULL ; queue<TreeNode*> que ; que.push(root) ; TreeNode* tmp = NULL ; bool zt = true ; int cur , precur = 0 ; while (!que.empty()) { tmp = que.front() ; que.pop() ; cur = tmp->val ; if ((cur & 1) != zt) return false ; if (cur == precur) return false ; if ((cur > precur) != zt) return false ; if (tmp->left) { que.push(tmp->left) ; nextN = tmp->left ; } if (tmp->right) { que.push(tmp->right) ; nextN = tmp->right ; } precur = cur ; if(!que.empty() && pre == tmp) { zt = (zt == true) ? false : true ; precur = zt ? (que.front()->val - 1) : (que.front()->val + 1) ; pre = nextN ; } } return true ; } };

复杂度计算：

时间复杂度： O(n) ； 空间复杂度： O(n)；