已知一棵完全二叉树,求其节点的个数

已知一棵完全二叉树,求其节点的个数

遍历算法时间复杂度是O(N),而遍历是低于O(N)的

我们可以利用满二叉树的结点个数为 2^h-1 (h为树的层数)来加速这个过程。

我们用h总 纪录变量最深到了哪一层
然后遍历x右子树的左边界
已知一棵完全二叉树,求其节点的个数
我们看右子树的左边界有没有到达最后一层

如果x的右子树的左边界已经到达最后一层
那么x的左子树就是满的 !
已知一棵完全二叉树,求其节点的个数
且左子树高度为h总-1

同时,因为左子树是满的,所以,其节点个数为 2^(h总-1)-1

算上根节点,其总的节点数为 2^(h总-1)

此时,根的右子树为完全二叉树,和母问题一致!可以用到递归了!

已知一棵完全二叉树,求其节点的个数
若右子树的左边界没有到最后一层,如下所示:
已知一棵完全二叉树,求其节点的个数
此时,右子树是满的!
是高度为2的满二叉树(比左树满的时候的高度要减1)
所以此时右树的节点是
已知一棵完全二叉树,求其节点的个数
此时,总的节点个数就是
已知一棵完全二叉树,求其节点的个数
而此时,左二叉树是一棵完全二叉树,接下来递归他!已知一棵完全二叉树,求其节点的个数
已知一棵完全二叉树,求其节点的个数
已知一棵完全二叉树,求其节点的个数
返回值是 以当前节点 node为头的 整棵树的 节点个数

已知一棵完全二叉树,求其节点的个数
复杂度怎么求:
已知一棵完全二叉树,求其节点的个数

遍历1节点是时候,发现右子树的最左节点已经到底了
已知一棵完全二叉树,求其节点的个数
每一层遍历的节点个数只有一个!
那么一共有多少层呢!
一共有

已知一棵完全二叉树,求其节点的个数
这么多个节点

每个节点要遍历其边界,
时间复杂度为
已知一棵完全二叉树,求其节点的个数
所以总的时间复杂度为:
已知一棵完全二叉树,求其节点的个数

初级5 02.44.37开始讲的