[数据结构与算法]完全二叉树的节点数

题目

分析

假设完全二叉树的高度为h，那么完全二叉树的节点数$$num=2^{(h?1)}?1+counter$$
counter是最后一层的节点数

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

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

    }
}*/
public class Solution {
     public int counter = 0;
    public int nodeNum(TreeNode head) {
        if(head == null) {
            return 0;
        }
        int hight = getHight(head);
        lastLevelNodeNum(head,0,hight-1);
        return (int)Math.pow(2,hight-1) - 1 + counter;
    }
    
    public int getHight(TreeNode root) {
        if(root == null) {
            return 0;
        }
        return Math.max(getHight(root.left),getHight(root.right)) + 1;
    }
   
    public void lastLevelNodeNum(TreeNode root,int level,int target) {
        if(root == null) {
            return;
        }
        if(level == target) {
            counter++;
            return;
        }
        lastLevelNodeNum(root.left,level + 1, target);
        lastLevelNodeNum(root.right,level + 1,target);
    }
}