Count Complete Tree Nodes

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

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

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.

Thoughts

https://discuss.leetcode.com/topic/15515/easy-short-c-recursive-solution/4

这道题本来想用二分法做，实现非常复杂还超时。后来看到别人的解法，可以看作是分治版本的改进，利用完全二叉树的性质，计算最左和最右的深度，如果深度相同代表是满的，直接返回；不同则调用原分治算法

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int leftHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return leftHeight(root.left) + 1;
    }

    private int rightHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return rightHeight(root.right) + 1;
    }

    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = leftHeight(root);
        int right = rightHeight(root);
        if (left == right) {
            return (1 << left) - 1; 
        } else {
            return countNodes(root.left) + countNodes(root.right) + 1;
        }
    }
}

Analysis

画个树能看出当不满时，会对不满的那条path走下去(O(h))，由于每一步需要O(h)算深度，总O(h^2).

参照分析

morrischen2008

Let n be the total number of the tree. It is likely that you will get a child tree as a perfect binary tree and a non-perfect binary tree (T(n/2)) at each level.

T(n) = T(n/2) + c1 lgn
       = T(n/4) + c1 lgn + c2 (lgn - 1)
       = ...
       = T(1) + c [lgn + (lgn-1) + (lgn-2) + ... + 1]
       = O(lgn*lgn)

每次有一半树是perfect tree. 下一次深度是上次深度减一, 因此是logn-1,不是lg(n-1).

(lgn)! = Θ((lgn)^(lgn) + 0.5e^(-lgn) )

lg(n!) = Θ(nlgn)

Ver.2

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

把高度定义为一直顺着左节点走能走的边个数. 算出当前节点左儿子和右儿子的高度, 当它们高度相同时, 意味着左子树是full tree，右边可能有空缺，把左子树的count算上; 否则右子树是full tree，同理。 一共lgN步, 每步算高度花费lgN, 因此lgN * lgN。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int countNodes(TreeNode* root) {
        const auto height = [&](TreeNode *cur) {
            int h = 0;
            while (cur != NULL) {
                cur = cur->left;
                ++h;
            }
            return h;
        };
        auto cur = root;
        int res = 0;
        while (cur != NULL) {
            int l = height(cur->left);
            int r = height(cur->right);
            if (l == r) {
                // left is a full tree: count = 2 ^ h - 1 + 1
                res += 1 << l;
                cur = cur->right;
            } else {
                // right is a full tree: 2 ^ r - 1 + 1
                res += 1 << r;
                cur = cur->left;
            }
        }
        return res;
    }
};