222.count-complete-tree-nodes 完全二叉树的节点个数

遍历法

遍历所有节点的方法，时间复杂度为\(O(n)\)

class Solution {
  public:
    int countNodes(TreeNode *root) {
        if (root == nullptr)
            return 0;
        int lc = countNodes(root->left);
        int rc = countNodes(root->right);
        return lc + rc + 1;
    }
};

利用完全二叉树的性质

如果一棵树是完全二叉树，那么如果左子树高度与右子树高度相等，那么左子树一定是满二叉树，节点数为\(2^h-1\)；如果左子树高度大于右二叉树，那么右子树一定是满二叉树，节点数为\(2^h-1\)。

#include <math.h>
class Solution {
  public:
    int getDp(TreeNode *root) {
        if (root == nullptr)
            return 0;
        int ldp = getDp(root->left);
        int rdp = getDp(root->right);
        return ((ldp < rdp ? rdp : ldp) + 1);
    }
    int countNodes(TreeNode *root) {
        if (root == nullptr)
            return 0;
        int lc, rc;
        if (getDp(root->left) == getDp(root->right)) {
            lc = pow(2, getDp(root->left)) - 1;
            rc = countNodes(root->right);
        } else {
            lc = countNodes(root->left);
            rc = pow(2, getDp(root->right)) - 1;
        }
        return lc + rc + 1;
    }
};