一颗完全二叉树上有1001个结点,求叶子节点个数
问题描述:
一颗完全二叉树上有1001个结点,求叶子节点个数
有种方法为什么能直接除以2向上取整就可以获得正确答案501了,
答
二叉树性质:n0 = n2 + 1
因为n0 + n1 + n2 = 1001
所以2n2 + 1 + n1 = 1001
由于该等式右边为奇数,左边的n1只能是偶数
又因为完全二叉树中度为1结点个数n1要么是0要么是1
所以只能是0
因此n2 = 500
所以n0 = 501