Balanced Binary Tree

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>