222. Count Complete Tree Nodes
给你一个完全二元树,判断该二元树共有几个节点。
限制:你必须设计一个小于O(n)时间的算法。
https://assets.leetcode.com/uploads/2021/01/14/complete.jpg
Input: root = [1,2,3,4,5,6]
Output: 6
思路:
1.如果一个树是一个完满(full)二元树,那么他的节点数量可以直接由高度计算
出来不需遍历每个节点(2^h-1)
2.题目给的测资都是完全二元树,一个完全二元树未必是一个完满二元树,但是
他的左树必定是一个完满二元树。
3.如果当前的树是一个完满二元树(左树高=右树高)直接套公式计算,否则对左树
和右树递回并+1(当前节点)
JavaCode: