Balanced Binary Tree.png
解題思路 ：
利用到取得 Maximum deep 的方式 檢查每個點的左, 右 child 高度差 如果出現差距大於 1 的情形代表已經失去平衡 就不再回傳高度而是 -1 同時只要有一層回傳 -1 代表整棵樹不平衡 所以繼續把 -1 回傳上去 不複雜但是容易忘記的題目
C++ code :
<pre><code>
/**
- Definition of TreeNode:
- class TreeNode {
- public:
int val;TreeNode *left, *right;TreeNode(int val) {this->val = val;this->left = this->right = NULL;}- }
*/
int getHeight(TreeNode *root)
{
if(root == nullptr) return 0;
int left = getHeight(root->left);
int right = getHeight(root->right);
if(left == -1 || right == -1 || abs(left - right) > 1)
{
return -1;
}
return 1 + max(left, right);
}
class Solution {
public:
/**
* @param root: The root of binary tree.
* @return: True if this Binary tree is Balanced, or false.
*/
bool isBalanced(TreeNode *root) {
// write your code here
if(root == nullptr) return true;
return getHeight(root) != -1;
}
};
<code><pre>
