题解 | #完全二叉树结点数#

思路

• 最直观的思路就是将所有的结点数一遍，这样得到最终结果的时间代价就是O(N)
• 上面一个方法忽略了我们的树是完全二叉树这一性质，完全二叉树满足的特点就是要么是一个满二叉树，要么除了最后一层以外其它层全满，最后一层的叶子结点必须从左到右不间隔的排布。
  • 虽然完全二叉树没有计算结点的方法
  • 但是满二叉树的结点数量满足2 ^ h - 1这一公式（h为树高），因此我们要在左右子树上对完全二叉树的情况进行简化数数的代价

方法一：直接数

class Solution {
public:
    int nodeNum(struct TreeNode* head) {
        if(head == NULL) return 0;                                // 如果当前结点为空，返回数量为0
        return 1 + nodeNum(head->left) + nodeNum(head->right);    // 如果当前结点非空，则以该节点为根节点的树的结点数量为1+左子树结点的数量+右子树结点的数量
    }
};

复杂度计算

• 时间复杂度：O(N)，因为对所有的结点访问
• 空间复杂度：O(N)，维护函数栈的空间大小

方法二：利用满二叉树的性质

一棵完全二叉树的左右子树一定有一边是满二叉树的，所以在递归的过程中实际上只会沿着其中的一个方向不断递归，因此递归的时间复杂度为O(logN)，每轮递归中又需要O(logN)的时间来计算深度，因此最终的时间复杂度降了下来。

class Solution {
public:
    int nodeNum(struct TreeNode* head) {
        int lh = 0;
        int rh = 0;
        TreeNode* l;
        TreeNode* r;
        for(l = head; l != NULL; l = l->left) lh++;                // 沿着左孩子数高度
        for(r = head; r != NULL; r = r->right) rh++;               // 沿着右孩子数高度
        if(lh == rh) return pow(2, lh) - 1;                        // 如果高度一致则说明是满二叉树直接用公式不递归
        return 1 + nodeNum(head->left) + nodeNum(head->right);     // 如果非满二叉树则需要继续递归
    }
};

复杂度计算

• 时间复杂度：O(logN * logN)，见前文描述
• 空间复杂度：O(logN)，栈空间的最大深度