AVL树高度求解

AVL树高度求解

我们这里求解高度的算法适用于所有二叉树

因为我们之前讲过了左旋转, 右旋转, 双旋转, 但是在实际编码中会有一个问题: 我们要确定LL型, LR型, RR型, RL型最小不平衡子树时需要通过求解最小不平衡子树根节点的左右子树高度差和最小不平衡的左(或右)子节点的左右子树的高度差来判断到底是那种类型的最小不平衡二叉树, 所以这里我们首要问题就是要求解对应结点的左右子树的高度差, 其实就是求树的高度后再作差

• 那么我们就要实现求树高度的算法?
  • 首先我们来进行思路分析:
    • 首先我们来编写求某个结点为根节点的树的高度, 我们要求树的高度, 那么就是要求该结点左右子树中比较高的子树的高度 + 1, 假如此时是该结点的左子树比较高, 那么这个时候求该结点的左子树的高度有可以看做是求这个左子节点的左右子树中比较高的子树的高度 + 1
      • 那么很明显,这个时候我们求解树高度的算法可以使用递归来是实现( 因为递归就是用来解决一个大规模问题可以化为多个小规模的同一问题的)

那么有了上面的思路分析之后, 我们的代码实现将会非常简单: (如下)

//返回以当前节点为根节点的树的高度
public int height(){
    return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
}
1
2
3
4

• 我们其实可以发现: 我们说用一行代码就计算出了树的高度
  • 其实这里的算法和迷宫回溯算法很相似, 此时我们是整个的将树走了一遍, 只不过通过三元运行算符最终实现了只返回最长路径的解

然后因为我们可能还需要有返回某个结点左子树和右子树高度的方法, 这里我们一并给出:

//返回左子树的高度
public int leftHeight(){
    if(left == null){
        //如果左子节点不存在, 那么就直接返回0即可
        return 0;
    }
    return left.height();
}

//返回右子树的高度
public int rightHeight(){
    if(right == null){
        //如果右子节点不存在, 那么就直接返回0即可
        return 0;
    }
    return right.height();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17