題目

給定一個(gè)二叉樹(shù)，判斷它是否是高度平衡的二叉樹(shù)。
本題中，一棵高度平衡二叉樹(shù)定義為：
一個(gè)二叉樹(shù)每個(gè)節(jié)點(diǎn) 的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1。
示例 1:
給定二叉樹(shù) [3,9,20,null,null,15,7]
3
/
9 20
/
15 7
返回 true 。
示例 2:
給定二叉樹(shù) [1,2,2,3,3,null,null,4,4]
1
/
2 2
/
3 3
/
4 4
返回 false 。

思路一：遞歸記錄每個(gè)結(jié)點(diǎn)的高度+層序遍歷檢查高度差

不過(guò)這樣的效率較低，畢竟遍歷了兩遍。

/*** 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()){//該層結(jié)點(diǎn)元素個(gè)數(shù) = 該層隊(duì)列元素int size = que.size();//這里要使用固定大小的size，不能使用que.size(),因?yàn)樵谔幚碇衠ue.size是不斷變化的//將這層元素送入隊(duì)列中并依次從隊(duì)首向隊(duì)尾將元素出隊(duì)列，每個(gè)元素出隊(duì)列的同時(shí)又將其不為空的子結(jié)點(diǎn)送入隊(duì)列for(int i =0;i<size;i++){TreeNode* node = que.front();//將隊(duì)首元素送入該層結(jié)果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;}}//將左右孩子結(jié)點(diǎn)入隊(duì)列，作為下一層的元素if(node->left) que.push(node->left);if(node->right) que.push(node->right);}}return true;} };

參考其他思路

概念辨析：
二叉樹(shù)結(jié)點(diǎn)的深度：指從根結(jié)點(diǎn)到該結(jié)點(diǎn)的最長(zhǎng)簡(jiǎn)單路徑邊的條數(shù)
二叉樹(shù)結(jié)點(diǎn)的高度：指從該結(jié)點(diǎn)到葉結(jié)點(diǎn)的最長(zhǎng)簡(jiǎn)單路徑邊的條數(shù)
leetcode中強(qiáng)調(diào)的深度和高度很明顯是按照結(jié)點(diǎn)來(lái)計(jì)算。
深度是從上到下去查，所以需要前序遍歷（中左右），而高度只能從下到上去查，所以只能使用后序遍歷（左右中）。
根結(jié)點(diǎn)的最大深度就是這個(gè)根結(jié)點(diǎn)的高度。
遞歸三部曲分析：
1、確定遞歸參數(shù)和返回值
參數(shù)：傳入的結(jié)點(diǎn)指針
返回值：返回傳入結(jié)點(diǎn)為根結(jié)點(diǎn)的樹(shù)的高度。
如果已經(jīng)不是二叉平衡樹(shù)了可以返回-1進(jìn)行標(biāo)記。

//-1 表示已經(jīng)不是平衡二叉樹(shù)了，否則返回值就是以該節(jié)點(diǎn)為更急誒·根結(jié)點(diǎn)的樹(shù)的高度(最大深度) int getDepth(TreeNode* node)

2、明確終止條件
遇到空結(jié)點(diǎn)終止，返回0

if(node ==NULL) return 0 ;

3、明確單層邏輯

1、如果左子樹(shù)不是平衡二叉樹(shù)，返回-1
2、如果右子樹(shù)不是平衡二叉樹(shù)，返回-1
3、如果左右子樹(shù)的高度差大于1，返回-1
4、否則，返回結(jié)點(diǎn)高度

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、舉例分析

以左側(cè)為例：
4：高度為 1
3：高度為 2
2：高度為3，它的左子樹(shù)高度為2，右子樹(shù)高度為0，高度差大于1，所以非平衡樹(shù)。
下面是我寫(xiě)的錯(cuò)誤的代碼，原因是對(duì)平衡二叉樹(shù)的理解出現(xiàn)了差錯(cuò)，是兩個(gè)子樹(shù)的高度差大于1。
而且考慮到出現(xiàn)一次非平衡狀態(tài)就直接返回-1，一直返回到原結(jié)點(diǎn)，從而減少時(shí)間浪費(fèi)。

錯(cuò)誤代碼：
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;} };

總結(jié)

了解了二叉樹(shù)的深度與高度的差異，求深度適合用前序遍歷，求高度適合用后序遍歷。

總結(jié)

以上是生活随笔為你收集整理的LeetCode 110. 平衡二叉树思考分析的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。