題目
給定一個二叉樹，判斷它是否是高度平衡的二叉樹。
本題中，一棵高度平衡二叉樹定義為：
一個二叉樹每個節點 的左右兩個子樹的高度差的絕對值不超過1。
示例 1:
給定二叉樹 [3,9,20,null,null,15,7]
3
/
9 20
/
15 7
返回 true 。
示例 2:
給定二叉樹 [1,2,2,3,3,null,null,4,4]
1
/
2 2
/
3 3
/
4 4
返回 false 。
思路一：遞歸記錄每個結點的高度+層序遍歷檢查高度差
不過這樣的效率較低，畢竟遍歷了兩遍。
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int getDepth(TreeNode* node){if(node == NULL) return 0;int left=getDepth(node->left);int right=getDepth(node->right);node->val = max(left,right)+1;return max(left,right)+1;}bool isBalanced(TreeNode* root) {getDepth(root);queue<TreeNode*> que;if(root!=NULL) que.push(root);int num=0;while(!que.empty()){//該層結點元素個數 = 該層隊列元素int size = que.size();//這里要使用固定大小的size，不能使用que.size(),因為在處理中que.size是不斷變化的//將這層元素送入隊列中并依次從隊首向隊尾將元素出隊列，每個元素出隊列的同時又將其不為空的子結點送入隊列for(int i =0;i<size;i++){TreeNode* node = que.front();//將隊首元素送入該層結果que.pop();if(node->left && node->right){if(abs(node->left->val - node->right->val)>1){return false;}}if(node->left && !node->right){if(node->left->val>1){return false;}}if(!node->left && node->right){if(node->right->val>1){return false;}}//將左右孩子結點入隊列，作為下一層的元素if(node->left) que.push(node->left);if(node->right) que.push(node->right);}}return true;}
};
參考其他思路
概念辨析：
二叉樹結點的深度：指從根結點到該結點的最長簡單路徑邊的條數
二叉樹結點的高度：指從該結點到葉結點的最長簡單路徑邊的條數
leetcode中強調的深度和高度很明顯是按照結點來計算。
深度是從上到下去查，所以需要前序遍歷（中左右），而高度只能從下到上去查，所以只能使用后序遍歷（左右中）。
根結點的最大深度就是這個根結點的高度。
遞歸三部曲分析：
1、確定遞歸參數和返回值
參數：傳入的結點指針
返回值：返回傳入結點為根結點的樹的高度。
如果已經不是二叉平衡樹了可以返回-1進行標記。
//-1 表示已經不是平衡二叉樹了，否則返回值就是以該節點為更急誒·根結點的樹的高度(最大深度)
int getDepth(TreeNode* node)
2、明確終止條件
遇到空結點終止，返回0
if(node ==NULL) return 0 ;
3、明確單層邏輯
1、如果左子樹不是平衡二叉樹，返回-1
2、如果右子樹不是平衡二叉樹，返回-1
3、如果左右子樹的高度差大于1，返回-1
4、否則，返回結點高度
int leftDepth = getDepth(node->left);
if(leftDepth == -1) return -1;
int rightDepth= getDepth(node->right);
if(rightDepth== -1) return -1;
if(abs(leftDepth - rightDepth)>1) return -1;
else return 1+max(leftDepth,rightDepth);
4、完整遞歸代碼
int getDepth(TreeNode* node)
{if(node ==NULL) return 0 ;int leftDepth = getDepth(node->left);if(leftDepth == -1) return -1;int rightDepth= getDepth(node->right);if(rightDepth== -1) return -1;if(abs(leftDepth - rightDepth)>1) return -1;else return 1+max(leftDepth,rightDepth);
}
5、舉例分析
以左側為例：
4：高度為 1
3：高度為 2
2：高度為3，它的左子樹高度為2，右子樹高度為0，高度差大于1，所以非平衡樹。
下面是我寫的錯誤的代碼，原因是對平衡二叉樹的理解出現了差錯，是兩個子樹的高度差大于1。
而且考慮到出現一次非平衡狀態就直接返回-1，一直返回到原結點，從而減少時間浪費。
錯誤代碼：
int getDepth(TreeNode* node) { if(node == NULL) return 0; int left=getDepth(node->left); int right=getDepth(node->right); if(node->left && node->right) { if(abs(left-right)>1) { return -1; } } if(node->left && !node->right) { if(left>1) { return -1; } } if(!node->left && node->right) { if(right>1) { return -1; } } return max(left,right)+1; }
AC代碼：
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int getDepth(TreeNode* node){if(node ==NULL) return 0 ;int leftDepth = getDepth(node->left);if(leftDepth == -1) return -1;int rightDepth= getDepth(node->right);if(rightDepth== -1) return -1;if(abs(leftDepth - rightDepth)>1) return -1;else return 1+max(leftDepth,rightDepth);}bool isBalanced(TreeNode* root) {if(getDepth(root)==-1) return false;return true;}
};
總結
了解了二叉樹的深度與高度的差異，求深度適合用前序遍歷，求高度適合用后序遍歷。
