222. Count Complete Tree Nodes

https://leetcode.com/problems/count-complete-tree-nodes/

Problem

Given a complete binary tree, count the number of nodes.

Note:

Definition of a complete binary tree from Wikipedia: In a complete binary tree every level, except possibly the last, is completely filled, 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.

Example:

Input: 
    1
   / \
  2   3
 / \  /
4  5 6

Output: 6

Solution

1. level order traversal

/**
 * 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 countNodes(TreeNode* root) {
        if (root == nullptr) return 0;
        int count = 0;
        vector<TreeNode*> current({root});
        vector<TreeNode*> next;
        while (!current.empty()) {
            next.reserve(current.size() * 2);
            count += current.size();
            for (const auto n: current) {
                if (n->left != nullptr) next.push_back(n->left);
                else break;
                if (n->right != nullptr) next.push_back(n->right);
                else break;
            }
            current.clear();
            current.swap(next);
        }
        return count;
    }
};

2. Recursive

/**
 * 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 countNodes(TreeNode* root) {
        if (root == nullptr) return 0;
        const int hl = height(root->left), hr = height(root->right);
        if (hl == hr) return (1 << hl) + countNodes(root->right);
        return (1 << hr) + countNodes(root->left);
    }
    inline int height(TreeNode *root) {
        if (root == nullptr) return 0;
        int h = 0;
        while (root != nullptr) {
            ++h;
            root = root->left;
        }
        return h;
    }
};

• #tree

• #levelorder

• #recursive