TOP101题解 | BM36#判断是不是平衡二叉树#
判断是不是平衡二叉树
https://www.nowcoder.com/practice/8b3b95850edb4115918ecebdf1b4d222
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * @author Senky * @date 2023.08.04 * @par url https://www.nowcoder.com/creation/manager/content/584337070?type=column&status=-1 * @brief 遍历二叉树,严格控制每一个结点的左右子树都是平衡二叉树 * (一)第一个左孩子,以其为根节点的树是否为平衡二叉树 * (二)第一个右孩子,以其为根节点的树是否为平衡二叉树 * (三)遍历每一个结点,并判断(一)、(二) * @param pRoot TreeNode类 * @return bool布尔型 */ //求树的高度 int maxDepth(struct TreeNode* root ) { // write code here if(root == NULL) { return 0; } int leftDepth = maxDepth(root->left); int rightDepth = maxDepth(root->right); return (leftDepth > rightDepth)?leftDepth + 1 : rightDepth + 1; } //当前结点是否为平衡二叉树 bool IsBalanced_Solution(struct TreeNode* pRoot ) { // write code here //空树必为平衡二叉树 if(pRoot == NULL) { return true; } int leftDepth = maxDepth(pRoot->left);//左子树的高度 int rightDepth = maxDepth(pRoot->right);//右子树的高度 //高度差大于1则不是平衡二叉树 if(abs(leftDepth - rightDepth) > 1) { return false; } //左右子树都是平衡二叉树 return IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right); }#TOP101#
TOP101-BM系列 文章被收录于专栏
系列的题解