1 题目描述
给出一个完全二叉树，求出该树的节点个数。
说明：
完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
输入:
1
/ \
2 3
/ \ /
4 5 6
输出: 62 题解
2.1 递归
def countNodes(self, root: TreeNode) -> int:
def fun(root):
if not root:
return 0
if not root.right and not root.left:
return 1
return fun(root.right) + fun(root.left) + 1
return fun(root)
2.2 完全二叉树的性质
先说完全二叉树的2个性质：
- 一个树若为完全二叉树，那么除最底层外，左右子树肯定也是满二叉树，
- 一颗完全二叉树的高度通过遍历左子树就可以获得
利用完全二叉树的性质便可以写出如下的代码：
左右子树的高度相同，说明什么，左子树都是满二叉树，那么遍历右子树就可以了(最后一层最后出现的节点肯定在右子树)
左右子树的高度不同，那么说明最底层有缺的，遍历左子树，最后一层最后出现的节点肯定在左子树
def get_height(root):
if not root:
return 0
res = 0
while root:
res += 1
root = root.left
return res
def method(self, root):
if not root:
return 0
lh = get_height(root.left)
rh = get_height(root.right)
if lh == rh:
return self.method(root.right) + (1 << lh)
else:
return self.method(root.left) + (1 << rh)解题思路
题解不讲武德，最关键的二分查找最后一层节点的没有讲透
但是搞明白之后，真的感觉数字很美妙
基础的：当我们在满的二叉树，从根节点一直向左走的时候，能得到层数n（root层为0号层，下一层是1号层。。。。。。）
那么整个树的节点数量就是[2^n, 2^(n+1)]个
以2层为例（层数是2，人看是三层的那种），整个树的数量应该在[4,7]之间
那么利用二分查找找到最后一层中间那个编号的节点 (4+7+1)/2=6,查找6号节点
6的二进制是->110,
此时，层数是2，那么从110的第二位开始寻找，查看1和0
0向左，1向右，所以从root出发，先→走，再←走，啪的一下找到6号元素，很快啊！！！！！
再举个例子，5号元素101，取后n层，01，就是root开始，向左再向右，找到5号，画画图就能明白了
配合二分查找的思想，如果6号存在，就去让左边界left变成的这个数，再进行下一步查找
如果不存在，右边界right变为这个数，再进行下一步二分查找
直到最后找到那个元素，就是答案（画画图 有助于理解）
代码
3 Definition for a binary tree node.
4 class TreeNode:
5 def init(self, x):
6 self.val = x
7 self.left = None
8 self.right = None
class Solution:
def countNodes(self, root: TreeNode) -> int:
if not root: return 0
level = 0
node = root.left
while node: # 这里获得层数
level += 1
node = node.left
l = 1<<level # 左界
r = (l<<1)-1 # 右界
while l < r:
mid = int((r+l+1)/2) # 中位
node = root
path = 1<<(level-1) # 取mid号数的后几位的模板
while node and path > 0:
if mid & path: node = node.right
else: node = node.left
path >>= 1 # 一层查完，查下一层
if node: l = mid # 存在left位置变化
else: r = mid-1 # 不存在right位置变化
return r # 年轻人耗子尾汁作者：kknike
链接：https://leetcode-cn.com/problems/count-complete-tree-nodes/solution/shu-zi-de-mei-gan-shen-de-qi-miao-by-kknike/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
