如何计算完全⼆叉树的结点数？
如何计算完全⼆叉树的结点数？要求：时间复杂度低于O(n)，即不能直接遍历⼆叉树。
答：从根节点开始，查看右⼦树的⾼度right_h与左⼦树的⾼度left_h的关系，如果right_h < left_h 说明右⼦树⼀定是满⼆叉树，左⼦树继续递归这个过程。如果right_h == left_h 说明左⼦树⼀定是满⼆叉树，右⼦树继续递归这个过程。
对于满⼆叉树，有这个公式，如果树的⾼度为k，则其结点数为2^k - 1。
左神的代码如下：太精辟了，递归函数的设计。时间复杂度O(logN*logN)
package class_04;
public class Code_08_CompleteTreeNodeNumber {
public static class Node {
public int value;完全二叉树算法
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
public static int nodeNum(Node head) {
if (head == null) {
return 0;
}
return bs(head, 1, mostLeftLevel(head, 1));
}
public static int bs(Node node, int level, int h) {  // level表⽰当前结点的深度，h整棵树的深度
if (level == h) {
return 1;
}
if (mostLeftLevel(node.right, level + 1) == h) {  // 表⽰左满
return (1 << (h - level)) + bs(node.right, level + 1, h);  // 左⼦树结点个数+当前结点，右⼦树继续递归
} else {
return (1 << (h - level - 1)) + bs(node.left, level + 1, h);
}
}
public static int mostLeftLevel(Node node, int level) {  // 求node结点的左⼦树深度，level当前结点深度
while (node != null) {
level++;
node = node.left;
}
return level - 1;
}
public static void main(String[] args) {
Node head = new Node(1);
head.left = new Node(2);
head.right = new Node(3);
head.left.left = new Node(4);
head.left.right = new Node(5);
head.right.left = new Node(6);
System.out.println(nodeNum(head));
}
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。