面试经典150题 P222 完全二叉树的节点个数

---

时间轴

时间轴

2025-10-29

init

---

题目：

P222 完全二叉树的节点个数

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

利用完全二叉树的性质：

• 完全二叉树的某一个结点的左子树或右子树必有一颗是满二叉树
• 完全二叉树的高度计算只需要从根节点一路向左记录高度即可

// 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 {
        // 计算高度
        fn height(mut node: Option<Rc<RefCell<TreeNode>>>) -> i32 {
            let mut h = 0;
            // 对于一颗完全二叉树，从根节点一直向左走可以算出完全二叉树的高度
            while let Some(n) = node {
                h += 1;
                node = n.borrow().left.clone();
            }
            h
        }

        match root {
            None => 0,
            Some(node) => {
                // 左子树高度
                let left_h = height(node.borrow().left.clone());
                // 右子树高度
                let right_h = height(node.borrow().right.clone());

                if left_h == right_h {
                    // 左子树高度 = 右子树高度，则左子树必定是满二叉树
                    // 高度为h的满二叉树有2^h - 1个结点, 加上根节点                    
                   1 + (1 << left_h) - 1 + Self::count_nodes(node.borrow().right.clone())
                } else { // left_h = right_h + 1
                    // 左子树高度 > 右子树高度，说明右子树必定是满二叉树
                   1 + (1 << right_h) - 1 + Self::count_nodes(node.borrow().left.clone())
                }
            }
        }
    }
}

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