题解 | 完全二叉树结点数

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
*/
#include< cmath > #用于pow()
#include< cstddef > #用于nullptr
#include< iostream > #用于cin cout
class Solution {
    //满二叉树的节点数是  2的层数次方-1，如果是满二叉树就可以直接计算
    //完全二叉树的子树也是完全二叉树，也就是说可以递归
    //完全二叉树的子树至少有一个满二叉树
    //如果左右子树层数相同则这个数就是满二叉树，如果左子树比右子树层数多则右子树一定是满二叉树
public:
    int nodeNum(TreeNode* head) {
        int L =0;
        int R =0;

        TreeNode* l;
        TreeNode* r;

        for(l=head; l != nullptr;l = l->left)L++;
        for(r=head; r != nullptr; r = r->right)R++;  //统计是不是满二叉树

        if(L == R) return pow(2, L)-1;  //是，则直接计算

        return 1 + nodeNum(head->left) + nodeNum(head->right);  //不是则继续求
    }
};