題目：輸入一棵二叉樹(shù)，判斷該二叉樹(shù)是否是平衡二叉樹(shù)。

?

分析：首先理解什么是平衡二叉樹(shù)。平衡二叉樹(shù)具有以下性質(zhì)：它是一 棵空樹(shù)或它的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1，并且左右兩個(gè)子樹(shù)都是一棵平衡二叉樹(shù)。

?

很明顯可以用遞歸解決。

解法一：

1 class Solution { 2 public: 3 int depth(TreeNode *pRoot) { 4 if (pRoot == nullptr) { 5 return 0; 6 } 7 int left = depth(pRoot->left); 8 int right = depth(pRoot->right); 9 return max(left, right) + 1; 10 } 11 bool IsBalanced_Solution(TreeNode* pRoot) { 12 if (pRoot == nullptr) { 13 return true; 14 } 15 int left = depth(pRoot->left); 16 int right = depth(pRoot->right); 17 return (abs(left - right) <= 1 && IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right)); 18 } 19 };

上述解法的不足在于在計(jì)算上層節(jié)點(diǎn)的時(shí)候，他會(huì)反復(fù)計(jì)算下層節(jié)點(diǎn)的深度，增加了時(shí)間復(fù)雜度，于是有了后序遍歷的解法，先判斷兩個(gè)子樹(shù)是否為平衡二叉樹(shù)，是的話返回深度，否則標(biāo)記為1.

解法二：后序遍歷

1 class Solution { 2 private: 3 int getdepth(TreeNode *pRoot) { 4 if (pRoot == NULL) { 5 return 0; 6 } 7 int left = getdepth(pRoot->left); 8 if (left == -1) { 9 return -1; 10 } 11 int right = getdepth(pRoot->right); 12 if (right == -1) { 13 return -1; 14 } 15 return abs(left - right) > 1 ? -1 : 1 + max(left, right); 16 } 17 public: 18 bool IsBalanced_Solution(TreeNode* pRoot) { 19 return getdepth(pRoot) != -1; 20 } 21 };

?

轉(zhuǎn)載于:https://www.cnblogs.com/qinduanyinghua/p/10474361.html

總結(jié)

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

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