完全二叉树_二叉树06

完全二叉树

以上方法都是按照普通二叉树来做的，对于完全二叉树特性不了解的同学可以看这篇 关于二叉树，你该了解这些！ (opens new window)，这篇详细介绍了各种二叉树的特性。

完全二叉树只有两种情况，情况一：就是满二叉树，情况二：最后一层叶子节点没有满。

对于情况一，可以直接用 2^树深度 - 1 来计算，注意这里根节点深度为1。

对于情况二，分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来计算。

完全二叉树（一）如图：

完全二叉树（二）如图：

可以看出如果整个树不是满二叉树，就递归其左右孩子，直到遇到满二叉树为止，用公式计算这个子树（满二叉树）的节点数量

java代码如下：

public int countNodes(TreeNode root) {
	if(root == null) return 0;
        int left = 0;
        int right = 0;
        TreeNode leftNode = root.left;
        TreeNode rightNode = root.right;
        while(leftNode != null) {
            left++;
            leftNode = leftNode.left;
        }
        while(rightNode != null) {
            right++;
            rightNode = rightNode.right;
        }
        
        if(left == right) {
            return (1 << (left+1)) - 1;
        } 
        return countNodes(root.left) + countNodes(root.right) + 1;
}