958. Check Completeness of a Binary Tree

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

Rust Solution

struct Solution;
use rustgym_util::*;
use std::collections::HashSet;

trait Postorder {
    fn postorder(&self, id: u32, nodes: &mut HashSet<u32>) -> usize;
}

impl Postorder for TreeLink {
    fn postorder(&self, id: u32, nodes: &mut HashSet<u32>) -> usize {
        if let Some(node) = self {
            let node = node.borrow();
            let left = node.left.postorder(id << 1, nodes);
            let right = node.right.postorder((id << 1) | 1, nodes);
            nodes.insert(id);
            left + right + 1
        } else {
            0
        }
    }
}

impl Solution {
    fn is_complete_tree(root: TreeLink) -> bool {
        let mut nodes: HashSet<u32> = HashSet::new();
        let count = root.postorder(1, &mut nodes);
        nodes.len() == count && nodes.into_iter().all(|x| x <= count as u32)
    }
}

#[test]
fn test() {
    let root = tree!(1, tree!(2, tree!(4), tree!(5)), tree!(3, tree!(6), None));
    let res = true;
    assert_eq!(Solution::is_complete_tree(root), res);
    let root = tree!(1, tree!(2, tree!(4), tree!(5)), tree!(3, None, tree!(7)));
    let res = false;
    assert_eq!(Solution::is_complete_tree(root), res);
}

Having problems with this solution? Click here to submit an issue on github.