【二叉树】奇偶树

0x00 题目

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

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

---

0x01 思路

因为要对每层数值进行判断处理
所以使用层序遍历方式
获取每层数值时
进行数值判断
以及递增判断

---

0x02 解法

语言：Swift

树节点：TreeNode

public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init() { self.val = 0; self.left = nil; self.right = nil; }
    public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
    public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
        self.val = val
        self.left = left
        self.right = right
    }
}

解法：

func isEvenOddTree(_ root: TreeNode?) -> Bool {
    guard let root = root else { return false }
    
    // 根节点为奇数
    // 1, 奇数, 0, 偶数
    var level: Int = 1
    var queue: [TreeNode] = []
    queue.append(root)
    
    while !queue.isEmpty {
        var temp: [TreeNode] = []
        var arr: [Int] = []
        
        // 判断每个值是否符合要求
        // 收集下一层节点
        for i in 0..<queue.count {
            let node = queue[i]
            if node.val % 2 != level {
                return false
            }
            arr.append(node.val)
            
            if let left = node.left {
                temp.append(left)
            }
            if let right = node.right {
                temp.append(right)
            }
        }
        
        // 偶数层，是递减的，反转一下，改成递增
        if level == 0 {
            arr.reverse()
        }
        
        // 递增判断
        for i in 1..<arr.count {
            if arr[i-1] >= arr[i] {
                return false
            }
        }
        
        // 下一层
        queue = temp
        // 切换奇偶
        level = (level == 1 ? 0 : 1)
    }
    
    return true
}

---

0x03 我的小作品

欢迎体验我的作品之一：小笔记-XNote
笔记好帮手
做笔记一步到位
App Store 搜索即可~

---