本文共 1001 字，大约阅读时间需要 3 分钟。

给出一个完全二叉树，求出该树的节点个数。

说明：

完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

示例:

输入:

输出: 6

方法一：

简单粗暴，每个结点都遍历一次，用时比较长，不过思路很清晰！

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

方法二：

获取左右子树的深度。左子树深度 hl ，右子树深度 hr。

有以下两种可能：

1.hl == hr：左子树为满二叉树，直接计算左子树的节点数，然后继续递归右子树。

public int countNodes(TreeNode root) {           if(root == null) return 0;                int hl = depth(root.left);        int hr = depth(root.right);        if(hl == hr) {               return   (int)Math.pow(2,hl)+ countNodes(root.right);         } else {               return   (int)Math.pow(2,hr) + countNodes(root.left);         }    }        private int depth(TreeNode node) {           int d = 0;        while(node != null) {               node = node.left;            d ++;        }                return d;    }

转载地址：http://ztmq.baihongyu.com/