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

完全二叉树

1. 普通二叉树的遍历，统计节点个数

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

2. 满二叉树的节点总数

public int countNodes(TreeNode root){
       int h = 0;    while (root != null){
           root = root.left;        h++;    }    //节点总数就是2^h - 1    return (int)Math.pow(2,h) - 1;}

3. 完全二叉树的节点总数

public int countNodes(TreeNode root){
           TreeNode l = root,r = root;        //记录左右子树高度        int hl = 0,hr = 0;        while (l != null){
               l = l.left;            hl++;        }        while (r != null){
               r = r.right;            hr++;        }        //如果左右子树的高度相同，说明是一颗满二叉树        if (hl == hr){
               return (int)Math.pow(2,hl) - 1;        }        //如果高度不同，则按照普通二叉树的逻辑计算        //但是两个递归只有一个会真的递归下去，另一个一定会触发hr == hl而立即返回，不会递归下去        return 1 + countNodes(root.left) + countNodes(root.right);    }