LeetCode222.完全二叉树的节点个数

题目描述

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

示例

提交的代码

你被骗了，我没写出来最优解。我自己的解题时复是O(n)，题目的进阶写法是设计出来一个时复小于n的，我没想出来。

学习到的方法

这里用到carl大佬的配图，自己懒得画了，我学到的这个方法也来自于人家的解答。链接：解答链接
图示：


完全二叉树的特性这里就不多说了，估计都知道，满二叉树的节点个数为2^h-1。这里的方法就是让左右两个指针分别向左和右下去，直到它们的left(右指针为right)为空，也就是分别统计左右子树的高度（因为是完全二叉树，可以这么求高度的），如果左右高度相同，那就用满二叉树的特性就可以求出当前树的节点个数；如果左右高度不同，那就递归下去。

class Solution {
    public int countNodes(TreeNode root) {
        if(root==null){
            return 0;
        }
        TreeNode left=root.left;
        TreeNode right=root.right;
        int lenLeft=0;
        int lenRight=0;
        int curHeight=0;
        while(left!=null){
            lenLeft++;
            left=left.left;
        }
        while(right!=null){
            lenRight++;
            right=right.right;
        }
        if(lenLeft==lenRight){
            return (2<<lenLeft)-1;
        }
        return countNodes(root.left)+countNodes(root.right)+1;
    }
}