完全二叉树的节点数

思路：

先理解下面两点：

1. 完全二叉树的子树也是完全二叉树
2. 完全二叉树的左右子树中至少有一颗是满二叉树

计算一颗满二叉树节点个数：

1.计算一颗满二叉树节点个数很简单，就等于2^h - 1 , h为该满二叉树的高度

问题在于如何确定那颗子树是满二叉树

1.如果左子树的高度等于右子树高度+1， 那么右子树必然是一颗满二叉树

2.如果左子树的高度等于右子树高度，那么左子树必然是一颗满二叉树

那么问题其实就解决了。下面开始技术总结

1.当前完全叉树的节点个数 = 一颗满二叉树节点个数 + 一颗完全二叉树节点个数
如果当前节点为 null， 自然以此为根的二叉树节点个数为0（也是递归出口）

2.一个查找完全二叉树树深度方法

public int nodeNum(TreeNode head) {
        if(head == null)
            return 0;
        int rightHeight = complateTreeHeight(head.right);
        int leftHeight = complateTreeHeight(head.left);
        if(rightHeight == leftHeight){
            //至少左子树是一颗满二叉树
            return (int)Math.pow(2, leftHeight)  + nodeNum(head.right);
        }else {
            return (int)Math.pow(2, rightHeight)  + nodeNum(head.left);
        }

    }


    public int complateTreeHeight(TreeNode root){
        //完全二叉树高度
        int count = 0;
        while (root != null){
            count++;
            root = root.left;
        }
        return count;
    }