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

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

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

    示例 1：
    奇偶树【队列】【递归】 - 图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：
    奇偶树【队列】【递归】 - 图2
    输入：root = [5,4,2,3,3,7]
    输出：false
    解释：每一层的节点值分别是：
    0 层：[5]
    1 层：[4,2]
    2 层：[3,3,7]
    2 层上的节点值不满足严格递增的条件，所以这不是一棵奇偶树。

    示例 3：
    奇偶树【队列】【递归】 - 图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, 10] 内
    • 1 <= Node.val <= 10

    分析：将二叉树按照层序遍历，并且在遍历的每一层从左到右判断结点值的奇偶性和严格递增递减性。

    方法1：获取二叉树的层序遍历结果，然后判断每一层的奇偶性和严格递增递减性。

    1. /**
    2.  * Definition for a binary tree node.
    3.  * struct TreeNode {
    4.  *     int val;
    5.  *     TreeNode *left;
    6.  *     TreeNode *right;
    7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
    8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    10.  * };
    11.  */
    12. class Solution {
    13. public:
    14.     // 二叉树层序遍历(递归方式)
    15.     void levelOrder(TreeNode *node, int depth, vector<vector<int>> &level_order)
    16.     {
    17.         if (!node)
    18.             return;
    19.         // 如果depth>=level_order.size()表明需要扩容
    20.         if (depth >= level_order.size())
    21.             level_order.push_back(vector<int> {});
    22.         level_order[depth].push_back(node->val);
    24.         levelOrder(node->left, depth+1, level_order);
    25.         levelOrder(node->right, depth+1, level_order);
    26.     }
    28.     // 数组为奇数递增
    29.     bool isOddAscendingOrder(vector<int> & nums)
    30.     {
    31.         int len = nums.size();
    32.         if (len > 1)
    33.         {
    34.             for(int i = 1; i < len; ++i)
    35.                 if (nums[i-1] >= nums[i])
    36.                     return false;
    37.             for(int i=0; i<len; ++i)
    38.                 if (nums[i] % 2 == 0)
    39.                     return false;
    40.         }
    41.         else if (len == 1)
    42.             if (nums[0] % 2 == 0)
    43.                 return false;
    45.         return true;
    46.     }
    48.     // 数组为偶数递减数组
    49.     bool isEvenDescendingOrder(vector<int> & nums)
    50.     {
    51.         int len = nums.size();
    52.         if (len > 1)
    53.         {
    54.             for(int i = 1; i < len; ++i)
    55.                 if (nums[i-1] <= nums[i])
    56.                     return false;
    57.              for(int i=0; i<len; ++i)
    58.                 if (nums[i] % 2 != 0)
    59.                     return false;
    60.         }
    61.         else if (len == 1)
    62.             if (nums[0] % 2 != 0)
    63.                 return false;
    64.         return true;
    65.     }
    67.     bool isEvenOddTree(TreeNode* root) 
    68.     {
    69.         vector<vector<int>> level_order;
    70.         levelOrder(root, 0, level_order);
    72.         int n = level_order.size();
    73.         bool ans = true;
    74.         for(int i=0; i<n; ++i)
    75.         {
    76.             if (i % 2 == 0)
    77.                 ans = ans && isOddAscendingOrder(level_order[i]);
    78.             else
    79.                 ans = ans && isEvenDescendingOrder(level_order[i]);
    80.         }
    81.         return ans;
    82.     }
    83. };

    方法2：采用队列，按照层序遍历二叉树，并在遍历的过程中判断每一层的奇偶性与严格递增(递减)性。

    1. class Solution {
    2. public:
    4.     // 数组为奇数递增
    5.     bool isOddAscendingOrder(vector<int> & nums)
    6.     {
    7.         int len = nums.size();
    8.         if (len > 1)
    9.         {
    10.             for(int i = 1; i < len; ++i)
    11.                 if (nums[i-1] >= nums[i])
    12.                     return false;
    13.             for(int i=0; i<len; ++i)
    14.                 if (nums[i] % 2 == 0)
    15.                     return false;
    16.         }
    17.         else if (len == 1)
    18.             if (nums[0] % 2 == 0)
    19.                 return false;
    21.         return true;
    22.     }
    24.     // 数组为偶数递减数组
    25.     bool isEvenDescendingOrder(vector<int> & nums)
    26.     {
    27.         int len = nums.size();
    28.         if (len > 1)
    29.         {
    30.             for(int i = 1; i < len; ++i)
    31.                 if (nums[i-1] <= nums[i])
    32.                     return false;
    33.              for(int i=0; i<len; ++i)
    34.                 if (nums[i] % 2 != 0)
    35.                     return false;
    36.         }
    37.         else if (len == 1)
    38.             if (nums[0] % 2 != 0)
    39.                 return false;
    40.         return true;
    41.     }
    43.     bool isEvenOddTree(TreeNode* root)
    44.     {
    45.         if (!root) return false;
    46.         bool ans = true;
    47.         queue<TreeNode *> Q;
    48.         Q.push(root);
    49.         int level = 0;
    50.         while(!Q.empty())
    51.         {
    52.             vector<int> nodes_val;
    53.             int len = Q.size();
    54.             for(int i=0; i<len; ++i)
    55.             {
    56.                 TreeNode * node = Q.front();
    57.                 Q.pop();
    58.                 nodes_val.emplace_back(node->val);
    59.                 if (node->left) Q.push(node->left);
    60.                 if (node->right) Q.push(node->right);
    61.             }
    62.             if (level % 2 == 0)
    63.                 ans = ans && isOddAscendingOrder(nodes_val);
    64.             else
    65.                 ans = ans && isEvenDescendingOrder(nodes_val);
    67.             level++;
    68.         }
    69.         return ans;
    70.     }
    71. };

    欢迎交流，批评指正！