剑指offer-平衡二叉树

    xiaoxiao2022-07-03  114

    题目描述:

    输入一棵二叉树,判断该二叉树是否是平衡二叉树。

    解题思路:

    采用前序遍历的递归算法思想。

    1)若二叉树为空,则高度为0,为平衡二叉树;

    2)若二叉树仅有根结点,则高度为1,为平衡二叉树;

    3)否则,对左右子树进行递归运算,判断左右子树是否同时满足平衡二叉树,如果满足,判断左子树和右子树的差,如果满足高高度差绝对值小于等于1,则此树为平衡二叉树,平衡二叉树的深度为左右子树中深的一边加上根结点;其他情况不是平衡二叉树。

    代码实现:

    最新回复(0)