1 | Given a complete binary tree, count the number of nodes. |
注意这个树是complete tree,也就是说,除了最后一层,其它层都是满的,且最后一层的所有节点是从左到右连续的
我们逐步从根节点向下试探,考虑根节点的高度和右子树的高度,如果他们高度差1,则说明右子树在整个树的最后一层是有节点的,因此可知左子树是满的,
所以节点数加上1<<根节点树高,然后向右子树走。否则说明最后一层的最右节点存在于左子树中,因此加上1<<(根节点高度-1),因为这一次只知道右子树是满的,且高度少1,这里我们每次都加了子树及根节点,所以是2的幂。并往左子树走。
1 | /** |