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

链接：

大意：

给定一棵完全二叉树，求二叉树的节点数。例子：

思路：

任意一种遍历方法都可以解决。

代码：

class Solution {    // 以任意一种遍历方法得到节点数    private int count = 0;    public int countNodes(TreeNode root) {        preOrder(root);        return count;    }    public void preOrder(TreeNode root) {        if (root == null)            return ;        count++;        preOrder(root.left);        preOrder(root.right);    }}

结果：

结论：

这种解法是对于任何树都适用的。对于完全二叉树，根据其不同于一般树的性质，应该是有另外更高效的解法的。（不过这种“不太高效”的方法也能打败100%，应该是测试用例太少了。。。） 

改进：

通过完全二叉树不同于一般二叉树的特性，可以计算出树的高度h以及最后一层的节点数order，然后返回 order + 2 ^ (h - 1) - 1即可。

class Solution {    private int order = -1; // 记录最后一个节点在其所在层的序号    public int countNodes(TreeNode root) {        int h = getHeight(root);        if (h == 0)            return 0;        getCountLastLayer(root, 1, h, 1);        return order + (1 << (h - 1)) - 1;    }    // 获得树的高度    public int getHeight(TreeNode root) {        if (root == null)            return 0;        return 1 + getHeight(root.left);    }    // 获得最后一个节点在其所在层的序号（即可知最后一层有多少个节点） num为当前节点在所在层的序号    public void getCountLastLayer(TreeNode root, int num, int h, int currLayer) {        if (currLayer == h) {            order = num;            return ;        }        if (root.right != null)            getCountLastLayer(root.right, num * 2, h, currLayer + 1);        if (order != -1) // 找到最后一个节点 直接return            return ;        if (root.left != null)            getCountLastLayer(root.left, num * 2 - 1, h, currLayer + 1);    }}

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