class Solution {
public:
int helper(TreeNode* root){
if (root == NULL) return -1;
int ldepth = helper(root->left);
int rdepth = helper(root->right);
if ((ldepth==-100) || (rdepth==-100)) return -100;
if (abs(ldepth-rdepth)< 2) return max(ldepth,rdepth)+1;
if (abs(ldepth-rdepth)>=2) return -100;
}
bool isBalanced(TreeNode *root) {
if (root==NULL) return true;
return ((helper(root)==-100)? false : true);
}
};
解法的巧妙之处在于帮助函数的返回值的选取,一方面我们需要返回每层递归的节点深度值,另一方面我们还需要将该返回值作为是否平衡的布值。求树的深度的问题是采用后序遍历的思想,因为树的深度是根节点左右子树深度的较大值,因此需要先求出左右子树的深度然后才可以最终确定根节点的深度,故需要采用后序遍历的深度搜索思想。
网友评论