题目 判断一棵树是否是完全二叉树 思路 完全二叉树 依序从左到右添加节点 。满二叉树是完全二叉树 完全二叉树不是满二叉树、 那么对于几个节点就可能出现4种情况 a.该节点左右孩子都存在。 b.该节点左孩子不不存在 右孩子存在 不是完全二叉树 c.该节点左孩子不存在 右孩子也不存在 是 d.该节点左右孩子都不存在 是 code /** * @author i * @create 2020/5/17 14:49 * @Description 判断一颗树是不是完全二叉树 * 完全二叉树 依序从左到右添加节点 。满二叉树是…

2020年5月17日 0条评论 9点热度 阅读全文

1.题目 已知一棵完全二叉树,求其节点的个数 要求:时间复杂度低于O(N),N为这棵树的节点个数 2.思路&code 2.1 思路 一般来说,我们遍历二叉树需要O(n)的时间复杂度,必须将每个节点进行统计才可以计算出节点的总数。 但是我们可以从完全二叉树的特点出发,完全二叉树只有当右子树满的情况,添加一个节点,会依序从左子树到右子树。 1.先递归查找二叉树的最高深度,也就是左子树的深度。high 2.然后将root.right 右子树的左子树的深度和最高深度high比较, a.如果右子树的左子树的深度等于h…

2020年5月17日 0条评论 9点热度 阅读全文