平衡二叉树

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

1.平均查找长度 ASL

2.平衡因子 BF = Hr - Hl

平衡二叉树

3.平衡二叉树高度

image.png

4.平衡二叉树的平衡

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

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

5.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;
    }