计算二叉树的高度可以采用几种不同的算法。
算法一：采用后序遍历二叉树，结点最大栈长即为二叉树的高度；
算法二：层次遍历二叉树，最大层次即为二叉树的高度；
算法三：采用递归算法，求二叉树的高度。

class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val) {
        this.val = val;
    }
}

public int height(TreeNode p) {  //p是一个二叉树根节点的引用
    if(p == null){
       return 0;
     }else{
       return 1 + max(height(p.left),height(p.right));
     }
}

满二叉树

对于一棵二叉树，如果每一个非叶子节点都存在左右子树，并且二叉树中所有的叶子节点都在同一层中，这样的二叉树称为满二叉树。

完全二叉树
对于一棵具有 n 个节点的二叉树按照层次编号，同时，左右子树按照先左后右编号，如果编号为 ii 的节点与同样深度的满二叉树中编号为 ii 的节点在二叉树中的位置完全相同，则这棵二叉树称为完全二叉树。

BST
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。

AVL 树（平衡二叉搜索树）
AVL 树是带有平衡条件的二叉查找树，一般是用平衡因子差值判断是否平衡并通过旋转来实现平衡，和红黑树相比，AVL 树是严格的平衡二叉树，平衡条件必须满足：所有节点的左右子树高度差的绝对值不超过 1。不管我们是执行插入还是删除操作，只要不满足上面的条件，就要通过旋转来保持平衡，而旋转是非常耗时的，由此我们可以知道 AVL 树适合用于插入与删除次数比较少，但查找多的情况。

局限性
由于维护这种高度平衡所付出的代价比从中获得的效率收益还大，故而实际的应用不多，更多的地方是用追求局部而不是非常严格整体平衡的红黑树。当然，如果应用场景中对插入删除不频繁，只是对查找要求较高，那么 AVL 还是较优于红黑树。
应用
windows 对进程地址空间的管理

红黑树
一种二叉查找树，但在每个节点增加一个存储位表示节点的颜色，可以是红或黑（非红即黑）。通过对任何一条从根到叶子的路径上各个节点着色的方式的限制，红黑树确保没有一条路径会比其它路径长出两倍，因此，红黑树是一种弱平衡二叉树（由于是弱平衡，可以看到，在 ** 相同的节点情况下，AVL 树的高度低于红黑树），相对于要求严格的 AVL 树来说，它的旋转次数少，所以对于搜索，插入，删除操作较多的情况下，我们就用红黑树 **。

性质
1. 每个节点非红即黑；
2. 根节点是黑的；
3. 每个叶节点（叶节点即树尾端 NULL 指针或 NULL 节点）都是黑的；
4. 如果一个节点是红的，那么它的两儿子都是黑的；
5. 对于任意节点而言，其到叶子点树 NULL 指针的每条路径都包含相同数目的黑节点；
应用
TreeMap，HashMap 的储存结构

 

智一面热门岗位面试题：

高级java工程师