完全二叉树的节点个数(力扣222)

这道题可以当成一般的二叉树直接遍历，但是我们如果利用完全二叉树的特点遍历，可以节省一些时间。不过时间复杂度两者其实都是O(n)。那么所谓的特点指的是什么呢？完全二叉树只有两种情况，要么是满二叉树，要么有一部分子树是满二叉树。我们可以统计子树的左右两侧节点，来判断该子树是否是满二叉树(注意仅限于这道题可以这样判断，因为在整棵树为完全二叉树的前提下，子树如果为满二叉树，那么它的左右两侧节点的高度一定相同)。这就导致了这道题与之前的题目最大的区别就是终止条件上。在写终止条件时，要计算以该父节点为根节点的子树的两侧节点高度，如果相同，则直接退出本层递归。这是本题大致思路，大家可以结合我下面的代码以及注释理解。

代码及注释如下：

/**
 * 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) {
        //终止条件1
        if(root == NULL) return 0;
        //终止条件2
        TreeNode* left = root -> left;
        TreeNode* right = root -> right;
        int leftDepth = 0,rightDepth = 0;
        while(left != NULL){
            left = left -> left;
            leftDepth++;
        }
        while(right != NULL){
            right = right -> right;
            rightDepth++;
        }
        if(leftDepth == rightDepth){
            return (1 << leftDepth + 1) - 1;//满二叉树可以直接用公式算
        }
        //递归左子树
        int leftTreeNum = countNodes(root -> left);
        //递归右子树
        int rightTreeNum = countNodes(root -> right);
        //处理逻辑：计算左右子树节点个数，返回给当前父节点
        int result = leftTreeNum + rightTreeNum + 1;
        return result;
    }
};