題目
輸入一顆二叉樹的根節(jié)點懈万，判斷該樹是不是平衡二叉樹查牌。如果某二叉樹中任意節(jié)點的左右子樹的深度相差不超過1蚜点，那么它就是一顆平衡二叉樹。例如下圖就是一顆平衡二叉樹
image.png
解題思路
- 用后序遍歷的方式遍歷二叉樹的每個節(jié)點先誉，那么在遍歷到一個節(jié)點之前就已經(jīng)遍歷了它的左湿刽、右子樹。
- 只要在遍歷每個節(jié)點的時候記錄它的深度(某一節(jié)點的深度等于它到葉節(jié)點的路徑的長度)褐耳，就可以一邊遍歷一邊判斷每個節(jié)點是不是平衡的诈闺。
代碼
class Solution{
public:
bool IsBalanced(BinaryTreeNode* pRoot)
{
int depth = 0;
return IsBalanced(pRoot,&depth);
}
bool IsBalanced(BinaryTreeNode* pRoot,int *pDepth)
{
if(pRoot == NULL)
{
*pDepth = 0;
return true;
}
int left,right;
//cout << "left: " << *left << "right: " << *right << endl;
if(IsBalanced(pRoot->left,&left) && IsBalanced(pRoot->right,&right))
{
int diff = left - right;
if(diff<=1 && diff>=-1)
{
*pDepth = 1+ (left>right?left:right);
return true;
}
}
cout << "left: " << left << "right: " << right << endl;
return false;
}
};
