1. 題目

給定一個(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 。限制： 1 <= 樹(shù)的結(jié)點(diǎn)個(gè)數(shù) <= 10000

《劍指Offer》同題：面試題55 - II. 平衡二叉樹(shù)

2. 解題

• 遞歸求二叉樹(shù)左右子樹(shù)高度
• 當(dāng)中任何一個(gè)的子樹(shù)高度差超過(guò)1，停止搜索
  

class Solution { public:bool isBalanced(TreeNode* root) {bool bal = true;balence(root,bal);return bal;}int balence(TreeNode* root, bool &bal) {if(!bal)return -1;if(root == NULL)return 0;int left_height = balence(root->left,bal);int right_height = balence(root->right,bal);if(abs(left_height-right_height)>1)bal = false;return max(left_height,right_height)+1;} };

class Solution {bool balanced = true; public:bool isBalanced(TreeNode* root) {depth(root);return balanced;}int depth(TreeNode* root){if(!balanced || !root)return 0;int depthL = depth(root->left);int depthR = depth(root->right);if(abs(depthL - depthR) > 1)balanced = false;return 1+max(depthL, depthR);} };

總結(jié)

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

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