平衡二叉树
平衡二叉树:平衡的搜索树
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;
}