题目描述
根据题目信息，我们可以整理出一些基本思路。
- 首先我们需要想办法遍历每层数据 其中需要记录二叉树当前深度。
- 遍历的过程中进行判断，不符合要求就返回false
基本就需要做到这两大板块就可以完成我们的任务了。重要的是这个过程如何实现：这里我们用到两个常用方法：广度优先搜索 （BFS）和 深度优先搜索（dfs）。下面初步解释一下两种算法：
广度优先搜索（BFS）
广度优先搜索是连通图的一种遍历算法，是很多重要图算法的原型（比如Dijkstra最短路径算法和Prim最小生成树算法）。它是一种盲目搜索法，目的是展开并检查图中的所有节点，进而得到结果。
过程是十分暴力的，不考虑结果的具体位置，直接遍历搜索所有节点，直到找到结果为止。基本过程是从根节点开始，沿着树（图）遍历所有节点，访问完所以节点后算法终止。常使用队列（FIFO）辅助实现BFS算法。
深度优先算法（DFS）
深度优先算法是图论的经典算法，是针对图和树的遍历算法（比如前序遍历，中序遍历，后序遍历）。利用深度优先算法可以产生目标图的对应拓扑排序表，进而方便的解决问题（如最大路径算法）。
其过程简单来说是对一个可能分支进行处理到不能再进行处理为止。如果是死路就返回，返回图中遇见未探索的分支就进行进行处理，直到达到要求。一般使用堆或栈来辅助实现DFS算法。
思路一（BFS）
根据上面的介绍我们可以通过队列来辅助我们进行遍历所有树。
具体分为两个循环嵌套：
- 首先外围while 保证访问所有节点，并记录深度。
- 内层for循环 负责处理该层所有节点，并将下一层节点存入队列中。
接下来是一些细节：
- leve记录层数 （注意从0开始）
- prev 记录上一个节点数
- value记录当前节点数
- prev 处理完每个节点后 需要迭代。
- 每层处理结束后 level++
这两个循环是算法的核心部分， 保证了遍历所有节点.
来看代码实现（选择使用C++ 比较方便）
class Solution {
public:
bool isEvenOddTree(TreeNode* root) {
//建立队列
queue<TreeNode*> qu;
//先入根节点
qu.push(root);
//设置层数
int level = 0;
//开始遍历 队列全为空就结束
while(!qu.empty()){
//prev 为前一个节点值 这里进行初始化
//偶数下标 层上的所有节点的值都是 奇整数，从左到右按顺序严格递增
//所以 prev设置为最小值
//奇数下标 层上的所有节点的值都是 偶整数，从左到右按顺序严格递减
//所以 prev设置为最大值
int prev = level % 2 == 0 ? INT_MIN : INT_MAX;
//获取当前层节点个数
int size = qu.size();
//进入该层循环
for(int i = 0 ; i < size ;i++){
//出队列 得到节点
TreeNode* node = qu.front();
qu.pop();
//获取当前节点值
int value = node->val;
//节点值 与 该层数奇偶不符 返回 false
if(value % 2 == level % 2) return false;
//偶数下标层 必须满足严格递增 通过当前值与上一个节点值进行判断
if(level % 2 == 0 && value <= prev) return false;
//奇数下标层 必须满足严格递减 通过当前值与上一个节点值进行判断
if(level % 2 == 1 && value >= prev) return false;
//进行入队列处理
if(node->left) qu.push(node->left);
if(node->right) qu.push(node->right);
//该节点结束 先前节点值迭代
prev = value;
}
//层数增加
level++;
}
//全部满足条件 返回真即可
return true;
}
};
来看效果：
过啦！！！ 大声欢呼！！！
思路二（DFS）
该思路使用递归，所以有点不太好理解，动态规划好DFS 的混合运算了属于。
我们写出的dfs函数主要完成以下工作：bool dfs(TreeNode* root,int p)
- root 为当前节点 p 为层数 dp[ p ]储存该层最新的数值
- 首先判断是否满足基本条件：
偶数下标 层上的所有节点的值都是 奇 整数，从左到右按顺序 严格递增
奇数下标 层上的所有节点的值都是 偶 整数，从左到右按顺序 严格递减
判断递增递减是通过 当前节点值与dp[ p ]的值进行比较
满足条件就更新dp[ p ] 值 - 然后进行下一层的判断
- 直到处理完所有数据。
//设置常量 方便使用
const int N = 1e5 + 7;
const int MAX = 0x3f3f3f3f;
class Solution {
public:
// dp[]数组储存上一个符合要求的值
int dp[N + 1];
bool dfs(TreeNode* root,int p){
//记录当前节点值
int value = root->val;
//奇数下标层 必须满足严格递减 通过当前值与上一个节点值进行判断
if(p & 1){
if(value & 1 || value >= dp[p]) return false;
}
//偶数下标层 必须满足严格递增 通过当前值与上一个节点值进行判断
else{
if(!(value & 1) || value <= dp[p]) return false;
}
//满足条件就更新数组值
dp[p] = value;
//继续深入处理
if(root->left && !dfs(root->left,p+1)) return false;
if(root->right && !dfs(root->right,p+1)) return false;
//符合要求 返回真
return true;
}
bool isEvenOddTree(TreeNode* root) {
for(int i = 0;i<N;i+=2) {
dp[i] = 0;//偶数下标 需要递增所以使用最小值0
dp[i + 1] = MAX;//奇数下标 需要递增所以使用最小值0
}
return dfs(root,0);
}
};
来看效果：
过啦！！！！！！！！！！！！！！！！！！！
这道题是我目前做过最难的题，虽然没有一遍做出来，但是参考大佬的代码，慢慢啃的感觉的真的很好。刷题继续！！！！！！
