题解 | #判断是不是平衡二叉树#
判断是不是平衡二叉树
https://www.nowcoder.com/practice/8b3b95850edb4115918ecebdf1b4d222
class Solution { public: int isIsBalancedAndHeight(TreeNode* pRoot) { //空树返回高度0 if(pRoot==nullptr) return 0; //获取子树高度(包含子树是否为平衡树的信息) int l=isIsBalancedAndHeight(pRoot->left); int r=isIsBalancedAndHeight(pRoot->right); if(l==-1||r==-1) { return -1; } else if(abs(l-r)>1) { return -1; }//以上两种情况可以判断该树不为平衡树 else { return max(l,r)+1; } } bool IsBalanced_Solution(TreeNode* pRoot) { int res=isIsBalancedAndHeight(pRoot); if(res==-1)//按照函数定义,-1代表不为平衡树 { return false; } else { return true; } } };
使用递归的方法解决此问题
1.空树为平衡树返回0
2.如果左右子树不都是平衡树,那么返回-1;
否则,判断1.根结点的左右子树高度差是否小于一,小于1返回-1,
2.否则返回当前树的高度给上一级,当前树的高度是容易得到的,因为其就等于左右子树的最高高度加1;
总结:
由于先假定能判断左右子树是否是平衡树倒推,这是后序遍历的思想