【二叉树】二叉树的完全性检验

0x00 题目

给定一个二叉树的 root
确定它是否是一个 完全二叉树

在一个 完全二叉树 中
除了最后一个节点外
所有节点都是完全被填满的
并且最后一个节点中的所有节点
都是尽可能靠左的
它可以包含 1 到 2h 节点之间的最后一级 h

---

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 isCompleteTree(_ root: TreeNode?) -> Bool {
    var queue: [TreeNode?] = []
    // 记录是否遍历到了 空节点
    var flag: Bool = false
    
    queue.append(root)
    while !queue.isEmpty {
        let node = queue.removeFirst()
        if node == nil {
            // 出现了空节点
            flag = true
            continue
        }else{
            // 出现空节点后，又出现了非空节点，所以不是完全二叉树
            if flag {
                return false
            }
            queue.append(node?.left)
            queue.append(node?.right)
        }
    }
    return true
}

---

0x03 我的作品

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

---