Given the root of a binary tree, determine if it is a complete binary tree.

In a complete binary tree, every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Example 1:

Input: root = [1,2,3,4,5,6]
Output: true
Explanation: Every level before the last is full (ie. levels with node-values {1} and {2, 3}), and all nodes in the last level ({4, 5, 6}) are as far left as possible.

Example 2:

Input: root = [1,2,3,4,5,null,7]
Output: false
Explanation: The node with value 7 isn’t as far left as possible.

Constraints:

• The number of nodes in the tree is in the range [1, 100].
• 1 <= Node.val <= 1000

---

1. BFS 遍历整棵树
2. 遍历过程中只要遇到一个是 None 的节点， 那剩下的节点必须都是 None， 否则一定不是完全二叉树

---

代码实现(Rust):

impl Solution {
    pub fn is_complete_tree(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
        let mut next_level: Vec<Option<Rc<RefCell<TreeNode>>>> = vec![root];
        let mut temp = Vec::new();
        let mut got_none = false;
        loop {
            while !next_level.is_empty() {
                if let Some(n) = next_level.remove(0) {
                    if got_none {
                        return false;
                    }
                    temp.push(n.borrow_mut().left.take());
                    temp.push(n.borrow_mut().right.take());
                } else {
                    got_none  = true;
                }
            }
            if temp.is_empty() {
                return true
            }
            next_level = temp.clone();
            temp.clear();
        }
    }
}