思路
二叉平衡树与它任意的子树都满足这样的性质:它们的左子树和右子树的深度只差小于等于一。
我们采用后序遍历的方式,以如下逻辑进行判断:
1)若当前节点为空,则返回0(穿过叶节点);
2) 若当前节点的左子树高度 == -1,表示左子树不平衡,直接返回 -1;若当前节点的右子树
高度 == -1,表示右子树不平衡,直接返回-1;
3)若当前节点的左子树深度与右子树深度只差小于等于一,则返回max(left, right) + 1,即当前节点的深度;
4)若当前节点的左子树深度与右子树深度只差大于一,不平衡,则返回 -1;
C++ 代码
class Solution {
public:
bool isBalanced(TreeNode* root) {
return dfs(root) != -1;
}
int dfs(TreeNode* root){//后序遍历的dfs
if(!root)//对应(1)
return 0;
int left = dfs(root->left);
if(left == -1)return left;
int right = dfs(root->right);
if(right == -1)return right;//对应(2)
if(abs(left - right) < 2)
return max(left, right) + 1;//对应(3)
else
return -1;//对应(4)
}
};