题解 | #完全二叉树结点数# | JAVA

计算左右节点数量可以这么算。 如果是一个普通2叉树

return 1 + countNodes(root.left) + countNodes(root.right);

如果是一个满2叉树 , 则套用公式 ， 2的树深次方-1

if (hl == hr) {
         return (int)Math.pow(2, deep) - 1;
     }

一个完全二叉树必然有一个满2叉 ， 然后整理代码如下：

/**
public class TreeNode {
 int val = 0;
 TreeNode left = null;
 TreeNode right = null;

 public TreeNode(int val) {
     this.val = val;

 }
}*/
public class Solution {
public int nodeNum(TreeNode head) {
     if (head == null) {
         return 0;
     }
    return countNodes(head);
 }

private 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++;
     }
// 按照满2叉树计算
     if (hl == hr) {
         return (int)Math.pow(2, hl) - 1;
     }
//按照普通计算
     return 1 + countNodes(root.left) + countNodes(root.right);
 }
}