首页 算法 二叉树

# 题目

给出一个完全二叉树，求出该树的节点个数。

示例 1：

  • 输入：root = [1,2,3,4,5,6]
  • 输出：6

示例 2：

  • 输入：root = []
  • 输出：0

示例 3：

  • 输入：root = [1]
  • 输出：1

提示：

  • 树中节点的数目范围是 [0, 5 * 10^4]
  • 0 <= Node.val <= 5 * 10^4
  • 题目数据保证输入的树是 完全二叉树

222. 完全二叉树的节点个数 - 力扣（LeetCode）

# 分析

完全二叉树就是除了底层可能没满其余层都满的二叉树

那么就分了两种情况，第一种最后一层满了也就是满二叉树，这种情况节点数为 2 的 n 次方 - 1。第二种情况最后一层没满，分别递归左右孩子，左右孩子一定会有是满二叉树的情况

class Solution {
public:
    int countNodes(TreeNode* root) {
        if (root == nullptr) return 0;
        TreeNode* left = root->left;
        TreeNode* right = root->right;
        int leftDepth = 0, rightDepth = 0; // 这里初始为 0 是有目的的，为了下面求指数方便
        while (left) {  // 求左子树深度
            left = left->left;
            leftDepth++;
        }
        while (right) { // 求右子树深度
            right = right->right;
            rightDepth++;
        }
        if (leftDepth == rightDepth) {
            return (2 << leftDepth) - 1; // 注意 (2<<1) 相当于 2^2，所以 leftDepth 初始为 0
        }
        return countNodes(root->left) + countNodes(root->right) + 1;
    }
};