网页网站设计公司排行榜桦甸网站开发定制

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

示例 ：

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

思想：

代码：

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

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