玩命加载中 . . .

222-完全二叉树的节点

LeetCode

发布日期: 2021-07-12

222. Count Complete Tree Nodes

Given the root of a complete binary tree, return the number of the nodes in the tree.

According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and $2^h$ nodes inclusive at the last level h.

Design an algorithm that runs in less than $O(n)$ time complexity.

Example 1:

Input: root = [1,2,3,4,5,6]
Output: 6

method 1: 递归

分别计算左节点数和右节点数，在加上当前节点的1

int countNodes(TreeNode* root) {
    if (root == nullptr) return 0;
    int leftNum = countNodes(root->left);
    int rightNum = countNodes(root->right);
    return leftNum + rightNum + 1;
}

时间复杂度：$O(n)$
空间复杂度：$O(n)$，算上了递归系统栈占用的空间

method 2: 层序遍历

累计每层的节点数

int countNodes(TreeNode* root) {
    queue<TreeNode*> q;
    if (root == nullptr) return 0;
    q.push(root);
    int count = 0;
    while (!q.empty()) {
        int size = q.size();
        count += size;  // 每一层的节点数
        for (int i = 0; i < size; ++i) {
            TreeNode* cur = q.front();
            q.pop();
            if (cur->left) q.push(cur->left);
            if (cur->right) q.push(cur->right);
        }
    }
    return count;
}

时间复杂度：$O(n)$
空间复杂度：$O(n)$

method 3: 利用完全二叉树性质

完全二叉树的根节点为第0层，最底层为第h层

则第$i$层的节点个数为

$0\leq i<h$时，第$i$层节点个数为$2^i$
$i=h$时，最底层节点个数最少为$1$，最多为$2^h$

如果是一棵满二叉树，则节点个数为

$2^0 + 2^1 + \cdots + 2^h = 2^{h+1}-1$

所以，如果能找到满二叉树的子树，就可以快速计算出该子树的节点数

左移一位是乘以2，右移一位是除以2

int countNodes(TreeNode* root) {
    if (root == nullptr) return 0;
    TreeNode* leftNode = root->left;
    TreeNode* rightNode = root->right;
    int leftDepth = 0, rightDepth = 0;
    while (leftNode) {
        leftNode = leftNode->left;
        leftDepth++;
    }
    while (rightNode) {
        rightNode = rightNode->right;
        rightDepth++;
    }
    if (leftDepth == rightDepth) {
        return (2 << leftDepth) - 1;    // 2的leftDepth+1次方
    }
    return countNodes(root->left) + countNodes(root->right) + 1;
}