判定给定二叉树示例是否为完全树、平衡树及AVL平衡树

你前半部分的理解有一点需要纠正：通常说完全二叉树属于平衡树，指的是它满足广义平衡要求（树高为节点数的对数级），但实际上所有符合严格定义的完全二叉树都天然满足AVL的平衡条件——因为完全二叉树“除最深层外其余层全满、最深层节点全部靠左排布”的填充规则，决定了树中任意节点的左右子树高度差绝对值不会超过1，不存在“是完全二叉树但不满足AVL平衡”的情况。
你给出的两个示例并不同时属于完全二叉树，二者都满足AVL平衡要求，具体判定过程如下：

• 完全二叉树：对树做层序遍历（从上到下逐层遍历，同层内从左到右访问节点），所有非空节点必须连续出现在遍历序列的前段，一旦出现空节点，序列后续不能再出现非空节点。
• AVL平衡：树中任意节点的左子树、右子树的高度差绝对值不能超过1（高度统一按“当前节点到其下最深叶子节点的路径节点数”计算，空树高度记为0，叶子节点高度记为1，计算标准统一时差值结果不受影响）。

Example A #

树结构如下：

4
        / \
       2   5
      /   /
     1   3

• 完全二叉树判定：它的层序遍历序列是4,2,5,1,null,3,null，可以看到遍历到节点1之后就出现了空节点（对应节点2的右孩子位置），但后续又出现了非空节点3（对应节点5的左孩子位置），说明最深层的节点没有从最左开始连续排列，中间留了空位，因此Example A不是完全二叉树。
• AVL平衡判定：逐节点计算高度差：
  • 叶子节点1、3高度为1，无孩子，高度差为0，符合要求；
  • 节点2：左子树（节点1）高度1，右子树为空高度0，差值为1，符合要求，自身高度为2；
  • 节点5：左子树（节点3）高度1，右子树为空高度0，差值为1，符合要求，自身高度为2；
  • 根节点4：左子树（以2为根的子树）高度2，右子树（以5为根的子树）高度2，差值为0，符合要求。
    因此Example A满足AVL平衡要求。

Example B #

树结构如下：

4
        / \
       2   5
      / \  
     1   3

• 完全二叉树判定：它的层序遍历序列是4,2,5,1,3,null,null，所有非空节点连续出现在序列前段，空节点之后没有其他非空节点；除了存放1、3的最深层外，上面两层都完全填充，最深层的两个节点也全部靠左排列，因此Example B是完全二叉树。
• AVL平衡判定：逐节点计算高度差：
  • 叶子节点1、3、5高度为1，无孩子，高度差为0，符合要求；
  • 节点2：左子树（节点1）高度1，右子树（节点3）高度1，差值为0，符合要求，自身高度为2；
  • 根节点4：左子树（以2为根的子树）高度2，右子树（节点5）高度1，差值为1，符合要求。
    因此Example B满足AVL平衡要求。

内容的提问来源于stack exchange，提问作者Sam Wong