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

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:

Input: 

    1    / \   2   3  / \  / 4  5 6

Output: 6

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/count-complete-tree-nodes 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

完全二叉树的节点数

一、遍历所有节点

二、这是完全二叉树，如果他是一个满二叉树，那么节点数 = 2 ^ 高度 - 1。此时可以判断根节点的左子树或者右子树是不是满二叉树。

判断方法，求出左子树的高度(只用判断跟节点到最左边的节点的高度)，如果左子树的高度等于右子树的高度，那说明左子树一定是满二叉树，右子树不一定是满二叉树，那么左子树的节点可以用 2 ^ 高度 - 1计算出，右子树继续遍历。

class Solution {    public int getLeftHight (TreeNode node){        if (node.left == null) {            return 1;        }        return getLeftHight(node.left) + 1;    }    public int countNodes(TreeNode root) {        int ans = 1;        if (root == null) {            return 0;        }        if (root.left == null) {            return 1;        }        if (root.right == null) {            return 2;        }        int leftLen = getLeftHight(root.left);        int rightLend = getLeftHight(root.right);        if (leftLen == rightLend) {            ans += (1 << leftLen) - 1;            ans += countNodes(root.right);        } else {            ans += countNodes(root.left);            ans += countNodes(root.right);        }        return ans;    }}