解题的关键在于 leftHeight 和 rightHeight 的获取。因为 C++不能有多个返回值，所以在这里用指针来传递高度信息。在递归中决定某个节点高度信息的就是该节点左右子树的高度，谁高就是谁 +1。如果节点为 NULL，那么它就是叶子节点，高度为 0。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
bool IsBalanced_Solution(TreeNode* pRoot) {
int height=0;
return this->isBalanced(pRoot,&height);
}
bool isBalanced(TreeNode* pNode, int* treeHeight){
if(pNode==NULL) {
*treeHeight=0;
return true;
};
int leftHeight,rightHeight;
bool isLeftBalance=this->isBalanced(pNode->left,&leftHeight);
bool isRightBalance=this->isBalanced(pNode->right,&rightHeight);
if(isLeftBalance && isRightBalance && (leftHeight-rightHeight<=1) && (leftHeight-rightHeight>=-1)){
*treeHeight=1+(leftHeight>rightHeight?leftHeight:rightHeight);
return true;
}
return false;
}
};
|
PS：最开始思路出问题了，没有重新计算高度树的高度，居然改了好几遍才过。sigh