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:

    1. Input: 
    2.     1
    3.    / \
    4.   2   3
    5.  / \  /
    6. 4  5 6
    8. Output: 6

    题意

    统计完全二叉树中的结点个数。

    思路

    不考虑完全二叉树性质的话，可以直接用递归处理。

    如果考虑完全二叉树的性质，可以如下操作：沿着左子树一直走得到最左边的高度leftHeight，沿着右子树一直走得到最右边的高度rightHeight，如果两者相等，说明当前树正好是满二叉树，可以直接计算得到结点个数；如果leftHeight > rightHeight，说明当前树是非满完全二叉树，递归处理左右子树即可。

    上述方法还可以进一步优化，使其每一次递归时只需要向一边递归，而不需要同时向两边递归(类似于二分查找)：计算左子树的高度leftHeight和右子树的高度rightHeight，如果两者相等，说明左子树是满二叉树，可以直接计算结点数，而右子树是完全二叉树(可能是满二叉树)，只需要向右子树递归即可；如果leftHeight > rightHeight，说明右子树是满二叉树，而左子树是完全二叉树，只需要向左子树递归即可。

    代码实现 - 递归

    1. class Solution {
    2.     public int countNodes(TreeNode root) {
    3.         return root == null ? 0 : 1 + countNodes(root.left) + countNodes(root.right);
    4.     }
    5. }

    代码实现 - 完全二叉树 1

    1. class Solution {
    2.     public int countNodes(TreeNode root) {
    3.         int leftHeight = 0, rightHeight = 0;
    5.         // 求最左边的高度
    6.         TreeNode x = root;
    7.         while (x != null) {
    8.             leftHeight++;
    9.             x = x.left;
    10.         }
    12.         // 求最右边的高度
    13.         x = root;
    14.         while (x != null) {
    15.             rightHeight++;
    16.             x = x.right;
    17.         }
    19.         if (leftHeight == rightHeight) {
    20.             return (1 << leftHeight) - 1;
    21.         } else {
    22.             return 1 + countNodes(root.left) + countNodes(root.right);
    23.         }
    24.     }
    25. }

    代码实现 - 完全二叉树 2

    1. class Solution {
    2.     public int countNodes(TreeNode root) {
    3.         if (root == null) {
    4.             return 0;
    5.         }
    7.         int leftHeight = getHeight(root.left);
    8.         int rightHeight = getHeight(root.right);
    10.         if (leftHeight == rightHeight) {
    11.             return 1 + (1 << leftHeight) - 1 + countNodes(root.right);
    12.         } else {
    13.             return 1 + (1 << rightHeight) - 1 + countNodes(root.left);
    14.         }
    15.     }
    17.     private int getHeight(TreeNode x) {
    18.         return x == null ? 0 : 1 + getHeight(x.left);
    19.     }
    20. }

    参考

    222. Count Complete Tree Nodes

    [LeetCode] 222. Count Complete Tree Nodes 求完全二叉树的节点个数