169.二叉树：完全二叉树的节点个数（力扣）

代码解决

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr, right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int countNodes(TreeNode* root) {
        if (root == nullptr) return 0; // 如果根节点为空，返回0

        TreeNode* left = root->left;
        TreeNode* right = root->right;
        int leftdeep = 0, rightdeep = 0;

        // 计算左子树的深度
        while (left) {
            left = left->left;
            leftdeep++;
        }

        // 计算右子树的深度
        while (right) {
            right = right->right;
            rightdeep++;
        }

        // 如果左子树深度和右子树深度相同，则这是一棵满二叉树
        if (leftdeep == rightdeep) {
            return (2 << leftdeep) - 1; // 满二叉树的节点总数
        }

        // 如果左子树深度和右子树深度不同，则递归计算左右子树的节点数
        return countNodes(root->left) + countNodes(root->right) + 1;
    }
};

代码使用了递归的方法。主要思路是首先判断根节点是否为空，如果为空，返回0。然后，分别计算左子树和右子树的深度。如果两者的深度相同，说明这是一棵满二叉树，其节点数可以通过公式 (2 << leftdeep) - 1 计算得出，其中 leftdeep 是左子树的深度。如果两者的深度不同，说明不是满二叉树，需要递归地计算左右子树的节点数，并将它们相加再加上根节点本身。

这里简要解释一下代码的工作流程：

1. 首先判断根节点是否为空，如果为空，返回0。
2. 初始化两个整数 leftdeep 和 rightdeep，分别用来记录左子树和右子树的深度，初始都为0。
3. 计算左子树的深度：
   • 从根节点的左子节点开始，不断向左移动，直到到达最左边的叶子节点。
   • 在这个过程中，leftdeep 增加。
4. 计算右子树的深度：
   • 从根节点的右子节点开始，不断向右移动，直到到达最右边的叶子节点。
   • 在这个过程中，rightdeep 增加。
5. 如果左子树深度等于右子树深度，说明这是一棵满二叉树，返回 (2 << leftdeep) - 1。
6. 如果左子树深度不等于右子树深度，说明不是满二叉树，递归地计算左右子树的节点数，并将它们相加再加上根节点本身。

这个算法的时间复杂度是 O(n)，因为每个节点都会被访问一次，其中 n 是树中节点的数量。空间复杂度也是 O(n)，因为需要存储递归调用的栈。