class Solution { public: bool ans = true;; bool isBalanced(TreeNode* root) { if(!root) return true; maxDepth(root); return ans; } int maxDepth(TreeNode* root) { if(root == NULL) return 0; //root的左、右子树的最大深度 int leftDepth = maxDepth(root->left); int rightDepth = maxDepth(root->right); if(abs(leftDepth-rightDepth) > 1){ ans =false; } //else ans=true;添加这行代码就会报错 //返回的是左右子树的最大深度+1 return max(leftDepth, rightDepth) + 1; } };
上面的代码添加一行后报错,如下代码解释了为什么
class Solution {
public:
bool ans = true;
bool isBalanced(TreeNode* pRoot) {
if(pRoot == NULL) return true;
//cout<<2<<endl;
treeDepth(pRoot);
//cout<<"ans ="<<ans<<endl;
return ans;
}
int treeDepth(TreeNode* root)
{
int k;
if(root == NULL) return 0;
int leftDepth = treeDepth(root->left);
// cout<<"leftDepth = "<<leftDepth<<endl;
int rightDepth = treeDepth(root->right);
// cout<<"rightDepth = "<<rightDepth<<endl;
k = abs(leftDepth - rightDepth);
cout<<"k = "<<k<<endl;
if(k <= 1)
{
ans = true;
cout<<"k <= 1, ans = true;"<<endl;
}
else
{
ans =false;
cout<<"k > 1 ,ans = true;"<<endl;
}
return max(leftDepth,rightDepth)+1;
}
};
递归会多次判断k的值,每判断一次就是对ans重新赋值。题目要求满足只要有一次K>1,ans = false,就不是平衡二叉树。
如果添加了else ans=true;存在一种情况:在最后一次执行递归函数的时候,刚好满足k<=1,ans = true,但在之前的若干次递归中,有ans = False.
class Solution { public: #计算树的深度 int treeDepth(TreeNode* root){ if(!root) return 0; return max(treeDepth(root->left),treeDepth(root->right))+1; } bool isBalanced(TreeNode* root) { if(!root) return true; int left = treeDepth(root->left); int right = treeDepth(root->right); #判断左右子树是否满足条件,然后如果满足条件,判断子树的子树是否满足条件,也就是本级递归的返回值 if(abs(left-right)<=1) return isBalanced(root->left)&&isBalanced(root->right); #如果不满足条件直接返回false else return false; } }; 作者:蜗牛壳 链接:https://www.acwing.com/solution/acwing/content/1779/ 来源:AcWing 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。