力扣110：判断二叉树是否为平衡二叉树

利用二叉树遍历的思想编写一个判断二叉树，是否为平衡二叉树

示例 ：

输入：root = [3,9,20,null,null,15,7]
输出：true

思想：

代码：

int getDepth(struct TreeNode* node) {
    //如果结点不存在，返回0
    if(node==NULL)
        return 0;
    //求出右子树深度
    int rightDepth = getDepth(node->right);
    //求出左子树深度
    int leftDepth = getDepth(node->left);
    //返回左右子树中的较大值+1
    return rightDepth > leftDepth ? rightDepth + 1 : leftDepth + 1;
}

bool isBalanced(struct TreeNode* root) {
    //递归结束条件为：传入结点为NULL，返回True
    if(root==NULL)
        return true;
    //求出左右子树的深度
    int leftDepth = getDepth(root->left);
    int rightDepth = getDepth(root->right);
    //若左右子树绝对值差距大于1，返回False
    if(abs(leftDepth - rightDepth) > 1 )
        return false;
    //检查左右子树是否为平衡二叉树
    return isBalanced(root->right) && isBalanced(root->left);
}

时间复杂度O（n）；空间复杂度O（1） 

原文地址：https://blog.csdn.net/m0_56332819/article/details/142729275

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！