Interview Classic 150 Problem P222 Count Complete Tree Nodes

---

Timeline

Timeline

2025-10-29

init

---

Problem:

P222 Count Complete Tree Nodes

https://leetcode.cn/problems/count-complete-tree-nodes/description/?envType=study-plan-v2&envId=top-interview-150

Use the properties of a complete binary tree:

• For any node in a complete binary tree, at least one of its left or right subtrees is a full binary tree.
• The height of a complete binary tree can be calculated by going left from the root and recording the height.

// Definition for a binary tree node.
struct Solution;

#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}
use std::cell::RefCell;
use std::rc::Rc;

impl Solution {
    pub fn count_nodes(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        // Calculate height
        fn height(mut node: Option<Rc<RefCell<TreeNode>>>) -> i32 {
            let mut h = 0;
            // For a complete binary tree, walking all the way left from the root gives its height.
            while let Some(n) = node {
                h += 1;
                node = n.borrow().left.clone();
            }
            h
        }

        match root {
            None => 0,
            Some(node) => {
                // Height of left subtree
                let left_h = height(node.borrow().left.clone());
                // Height of right subtree
                let right_h = height(node.borrow().right.clone());

                if left_h == right_h {
                    // If the height of the left subtree equals the height of the right subtree, then the left subtree must be a full binary tree.
                    // A full binary tree of height h has 2^h - 1 nodes, plus the root node.                    
                   1 + (1 << left_h) - 1 + Self::count_nodes(node.borrow().right.clone())
                } else { // left_h = right_h + 1
                    // If the height of the left subtree is greater than the height of the right subtree, then the right subtree must be a full binary tree.
                   1 + (1 << right_h) - 1 + Self::count_nodes(node.borrow().left.clone())
                }
            }
        }
    }
}

fn main() {
    println!("Hello, world!");
}