文章目录

• 思路
• 代码

思路

Height函数：
p为平衡二叉树时，正常返回p的高度；否则返回-1

若某结点返回值为-1，说明这个结点的左右子树不平衡，此时该结点的父结点接收到的子树高度为-1，则父结点的left值=0，继续返回-1

说明只要有一个点不平衡，那么这个信息(不平衡)将会向上传递，表现在数值上就是最后返回root高度为-1
若每个点都是平衡的，则正常返回root的高度，因为每个点都是平衡的，Height函数的出口只会在第一个return，不会执行到”return -1;”，此时就意味着该函数是一个返回root高度的函数

代码

int Height(struct TreeNode *p){if(p==NULL) return 0;int left=1+Height(p->left), right=1+Height(p->right);if(left>0  && right>0 && pow((left-right),2)<=1)return left>right? left:right;return -1;}bool isBalanced(struct TreeNode* root){int l=Height(root);return l>=0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！