題目
題目：輸入一棵二叉樹座柱，判斷該二叉樹是否是平衡二叉樹迷帜。
注：這個題思路很好，可以經(jīng)成矗看戏锹。
解法一
思路
一般來說，平衡二叉樹既是平衡的樹火诸，又是二分搜索樹锦针。但此題只要求判斷是不是平衡的。
判斷一棵樹是否是平衡的置蜀，就是判斷所有的節(jié)點是不是平衡的奈搜。
判斷一個節(jié)點是不是平衡的，就是判斷左右子節(jié)點的高度差是否<=1盯荤。
如果學(xué)過AVL樹馋吗，思路是一樣的，但是卻有一點不同秋秤，AVL樹的TreeNode結(jié)構(gòu)體(每個節(jié)點)中有一個成員表示高度宏粤，在每次插入節(jié)點的時候就會更新每個節(jié)點的高度，所以判斷是否平衡的時候可以直接判斷是否為平衡的灼卢。
而這個題的TreeNode結(jié)構(gòu)體如下所示：
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
這個結(jié)構(gòu)體并沒有保存高度信息绍哎，所以第一個想法是寫一個求高度的函數(shù)，分別對左右子樹求高度鞋真，再看高度差受否滿足平衡二叉樹的要求崇堰。
求樹的高度可以使用遞歸法，樹的高度等于左右子樹高度的最大值再加上1（自身節(jié)點高度為1）灿巧，遞歸代碼如下：
int getHeight(TreeNode *node){
if(node == NULL)
return 0;
return 1 + max(getHeight(node->left), getHeight(node->right));
}
判斷當(dāng)前節(jié)點是否平衡赶袄，就是計算左右子樹的高度差揽涮。
判斷當(dāng)前樹是不是平衡，就是判斷當(dāng)前節(jié)點饿肺、當(dāng)前節(jié)點的左子樹蒋困、當(dāng)前節(jié)點的右子樹是否平衡，還是個遞歸問題敬辣。
代碼
class Solution {
public:
// 遞歸求高度
int getHeight(TreeNode *node){
if(node == NULL)
return 0;
return 1 + max(getHeight(node->left), getHeight(node->right));
}
//判斷該節(jié)點是否平衡
bool IsBalanced(TreeNode *node){
if(node == NULL)
return true;
if(abs(getHeight(node->left) - getHeight(node->right)) > 1)
return false;
return true;
}
bool IsBalanced_Solution(TreeNode* pRoot) {
if(pRoot == NULL)
return true;
return IsBalanced(pRoot) && IsBalanced(pRoot->left) && IsBalanced(pRoot->right);
}
};
代碼提交后雪标，成功過關(guān)。
解法二
思路
雖然成功的做出了這個題溉跃，但是總覺得有很別扭的地方村刨。
為了求判斷某個節(jié)點是不是平衡，需要求左右子樹的高度撰茎，判斷完該節(jié)點之后嵌牺，又需要判斷左子樹是不是平衡，這個時候又需要計算左子樹的左右子樹的高度龄糊，講道理逆粹，第一次遞歸求根節(jié)點的高度時，下面的節(jié)點的高度已經(jīng)被計算過了炫惩，但是卻沒有被記錄下來僻弹，導(dǎo)致白白遍歷了很多次。
借鑒動態(tài)規(guī)劃中的記憶化搜索他嚷，可以使用map<TreeNode*, int> mp來記錄每個節(jié)點的高度蹋绽，如果發(fā)現(xiàn)計算過，就直接返回記錄的值筋蓖。
這樣應(yīng)該能解決重復(fù)遞歸的問題卸耘，但是又增加了空間復(fù)雜度。
看了下別人的思路扭勉，豁然開朗鹊奖。原先的做法中，在求當(dāng)前節(jié)點的高度時涂炎，遞歸計算下面了所有節(jié)點的高度忠聚，但是卻沒有充分利用這些高度值。其實這個時候可以多做一件事情唱捣，判斷該節(jié)點是不是平衡的两蟀！如果不平衡，可以提前結(jié)束遞歸震缭。
代碼
class Solution {
public:
int getHeight(TreeNode *node){
if(node == NULL)
return 0;
int left = getHeight(node->left); //求左子樹的高度
if(left == -1) return -1; //求左子樹的高度的時候發(fā)現(xiàn)了該節(jié)點不平衡
int right = getHeight(node->right);
if(right == -1) return -1;
return abs(left - right) > 1 ? -1 : 1 + max(left, right); //求該節(jié)點的高度
}
bool IsBalanced_Solution(TreeNode* pRoot) {
return getHeight(pRoot) != -1;
}
};
思路還是有點繞赂毯，舉個栗子：
如上圖，遞歸的步驟是：
- 求節(jié)點
1的高度時，遞歸到了葉子節(jié)點4党涕，左右節(jié)點的高度值都為0烦感，可以判斷出節(jié)點4是平衡的，所以求的節(jié)點4的高度值為1膛堤，并將這個高度值返回遞歸的上一層Ｊ秩ぁ！肥荔！ - 這時返回上一層绿渣，到了節(jié)點
3。它得到到了左節(jié)點4的高度值1燕耿，繼續(xù)遞歸計算右節(jié)點的高度中符，得到高度值0，所以節(jié)點3滿足平衡條件誉帅，且自身的高度值為2淀散，又將這個高度值返回給上一層。 - 又返回了上一層堵第，到了節(jié)點
2吧凉。它得到到了左節(jié)點3的高度值2隧出，繼續(xù)遞歸計算右節(jié)點的高度踏志，得到高度值0，這個時候就發(fā)現(xiàn)節(jié)點2是不平衡的了胀瞪！沒有必要繼續(xù)再計算高度了针余，直接層層返回失敗就行了。由于返回值是int凄诞，所以設(shè)定返回-1就是失敗圆雁。這也就是為什么需要在得到高度后判斷是不是-1的原因。 - 最后只需要保證根節(jié)點的高度值不是-1就說明是這棵樹是平衡的了
總結(jié)
遞歸是個大殺器帆谍，也難以利用伪朽，不要重復(fù)遞歸。
遞歸說到底還是個棧汛蝙，只是利用了函數(shù)調(diào)用形成的棧烈涮。
