Leetcode Study Day 38

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 2h 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
Example 2:

Input: root = []
Output: 0
Example 3:

Input: root = [1]
Output: 1
 

Constraints:

The number of nodes in the tree is in the range [0, 5 * 104].
0 <= Node.val <= 5 * 104
The tree is guaranteed to be complete.

Solution

We create two functions, countLeft and countRight to count the layer of left and right subtree. If they are equal, we can use the formula (number of nodes equals to 2**layer - 1) to calculate the number of nodes. Otherwise, we plus one and recursively call the function to count the number of nodes in the left and right subtree.

/**
 * 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 countLeft(TreeNode* node){
        if (!node)
            return 0;
        if (!node->left){
            return 1;
        }
        else
            return 1 + countLeft(node->left);
    }
    int countRight(TreeNode* node){
        if (!node)
            return 0;
        if (!node->right){
            return 1;
        }
        else
            return 1 + countRight(node->right);
    }

    int countNodes(TreeNode* root) {
        if(!root)
            return 0;
        int layerLeft = countLeft(root);
        int layerRight = countRight(root);
        if (layerLeft == layerRight)
            return pow(2,layerLeft) - 1;
        else
            return (1+countNodes(root->left)+countNodes(root->right));
    }
};