|
这张图中，绿色树是满二叉树，当去掉7号节点，变成了黄色树。
这颗黄色树的序号相对于满二叉树的序号都能一一对应，所以这个黄色树就是完全二叉树。
如果去掉的是6号节点，变成红色树，这时候，红色树的节点就必须有所变化了，6消失后节点7必须变成节点6才正确。
所以这个红色树就不是完全二叉树，因为它相对于满二叉树序号有所改变，已经对应不上了。
算法——平衡二叉树
说了这么多，该来个题练练手了。
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。回 true 。
解析
题目给出了平衡二叉树的概念，就是任意节点的左右子树相差不超过1，就是平衡二叉树。
那这个深度是啥呢?
深度就是根节点到当前节点经过的边个数
层数就是当前节点在第几层，跟节点为第一层，所以层数=深度+1
法1
首先容易想到的就是把每个节点的深度都算出来，然后进行左右节点比较就能得出是不是平衡二叉树。
那么节点的子树深度怎么计算呢?
递归。当子节点为空就返回，否则每次增加一个单位深度。节点开始，计算每个左子树深度和右子树深度的差值，以及下面的每个节点的左子树和右子树深度，最终得出结果。
这种先处理节点，在处理左子树，再处理右子树 的遍历方式叫做 前序遍历或者先序遍历。
时间复杂度
假设节点总数为n，层数为x，二叉树为满二叉树。
时间复杂度计算可以通过 每层的时间复杂度 * 层数复杂度
每层的时间复杂度：
-
第一层需要遍历n次，第二层需要遍历n-1次，第三层需要遍历n-3次，所以每层的时间复杂度为O(n)
层数复杂度：
-
第一层为1个节点，第二层为2个节点，第三层为4个节点，第x层为2的x-1
（编辑：甘孜站长网）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
