[binary tree] completeness test of binary tree

0x00 subject

Given a binary tree root
Determine if it's a Perfect binary tree

In a Completely Binary tree in
except Last Outside a node
All nodes are Completely Filled
And all nodes in the last node
As far as possible Keep to the left Of
It can contain 1 To 2h The last level between nodes h

---

0x01 Ideas

According to the definition of complete binary tree
Under what circumstances is No Complete binary tree ？
It's the emergence of Empty child nodes Then it appeared again Non empty child node

---

0x02 solution

Language ：Swift

Tree node ：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
    }
}

solution ：

func isCompleteTree(_ root: TreeNode?) -> Bool {
    var queue: [TreeNode?] = []
    //  Whether the record traverses to   Blank nodes 
    var flag: Bool = false
    
    queue.append(root)
    while !queue.isEmpty {
        let node = queue.removeFirst()
        if node == nil {
            //  An empty node appears 
            flag = true
            continue
        }else{
            //  After an empty node appears , Non empty nodes appear again , So it's not a complete binary tree 
            if flag {
                return false
            }
            queue.append(node?.left)
            queue.append(node?.right)
        }
    }
    return true
}

---

0x03 My work

Welcome to experience one of my works ： Little notes -XNote
Take notes one step at a time
App Store Search ~

---