平衡二叉树

平衡二叉树：平衡的搜索树

1.平均查找长度 ASL

2.平衡因子 BF = Hr - Hl

平衡二叉树

3.平衡二叉树高度

4.平衡二叉树的平衡

在插入某结点后平衡树失去平衡，因此调整。

5.判断是否为平衡二叉树问题

5.1 求高度问题-> 后序遍历

• 首先一个树是平衡二叉树则子树全是平衡二叉树，因此递归判断子树
• 确定函数返回值为此时根结点高度
• 中止条件为 root 为空返回 0
• 每次之间的逻辑为返回左右子树结点的最大高度，为此时根结点的高度，并且子树非平衡树时直接返回-1此后都无需判断。

    int getdepth(TreeNode* root)
    {
        if(root == nullptr)
            return 0;
        if(getdepth(root->left) == -1) return -1;
        int depthLeft = getdepth(root->left);
        if(getdepth(root->right) == -1) return -1;
        int depthRight = getdepth(root->right);
        return abs(depthLeft-depthRight) <=1 ? 1+max(depthRight,depthLeft) : -1;
    }
    bool isBalanced(TreeNode* root) {
           return getdepth(root) == -1 ? false : true;
    }