1609. 奇偶树
如果一棵二叉树满足下述几个条件,则可以称为 奇偶树 :
二叉树根节点所在层下标为 0 ,根的子节点所在层下标为 1 ,根的孙节点所在层下标为 2 ,依此类推。
偶数下标 层上的所有节点的值都是 奇 整数,从左到右按顺序 严格递增
奇数下标 层上的所有节点的值都是 偶 整数,从左到右按顺序 严格递减
给你二叉树的根节点,如果二叉树为 奇偶树 ,则返回 true ,否则返回 false 。
/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) { * this.val = val; * this.left = left; * this.right = right; * } * } */ public class Solution { public bool IsEvenOddTree(TreeNode root) { Queue<TreeNode> queue = new Queue<TreeNode>(); queue.Enqueue(root); int level = 0; //从第0层开始 while (queue.Count > 0) { int size = queue.Count; int prev = level % 2 == 0 ? int.MinValue : int.MaxValue; //如果是偶数层 就取最小值 因为要严格递增 //如果是奇数层 就取最大值 因为要严格递减 for (int i = 0; i < size; i++) { TreeNode node = queue.Dequeue(); //取出节点 int value = node.val; if (level % 2 == value % 2) { return false; } //如果层是偶数但是值也是偶数就不符合条件 if ((level % 2 == 0 && value <= prev) || (level % 2 == 1 && value >= prev)) { return false; } //判断偶数层严格递增 奇数层严格递减 prev = value; //比较的值变成了当前节点 if (node.left != null) { queue.Enqueue(node.left); } //左节点不为空 就进入队列 if (node.right != null) { queue.Enqueue(node.right); } //右节点不为空 就进入队列 } level++; //下一层 } return true; } }
广度优先 或者说是层序遍历
在遍历的同时加上判断条件
只要遍历到了不符合条件的情况
就可以直接返回无需继续遍历