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

完全二叉树节点数目计算方法

在计算完全二叉树的节点数目时，可以选择以下两种方法：

方法一：递归遍历法

这种方法简单直接，通过递归遍历每个节点来计算总数。具体实现如下：

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

这种方法的时间复杂度是O(n)，其中n为树的节点数。它的逻辑简单且容易实现，适用于大多数情况。

方法二：基于深度的计算法

这种方法利用了完全二叉树的高度特性，通过计算左右子树的深度来确定节点数目。具体实现如下：

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;
}

这种方法的时间复杂度是O(h)，其中h为树的高度，通常比方法一更高效，特别是在处理大树时表现更好。

选择方法的建议

• 如果树的高度较低且节点数较少，方法一可能更适合。
• 如果树的高度较高或节点数较多，方法二可能更高效。

通过以上两种方法，可以准确计算完全二叉树的节点数目，满足不同的性能需求。

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