# 平衡二叉樹

## 平衡二叉樹

-1 <=左子樹的高度–右子樹的高度<= 1

## 平衡二叉樹的幼稚方法

1. 從根開始。 如果根為null，則返回true。
2. 計算其左右子樹的高度，並將它們分別存儲在名為leftHeight和rightHeight的變量中。
3. 遞歸調用根的左右子樹的平衡高度函數。 如果左右子樹均已平衡，並且leftHeight和rightHeight之間的差小於或等於1，則返回true，否則返回false。

### JAVA代碼

```public class BalancedBinaryTree {
static class Node {
int data;
Node left;
Node right;

public Node(int data) {
this.data = data;
left = right = null;
}
}

// Function to calculate height of a tree rooted at root
private static int height(Node root) {
if (root == null) {
// Height of empty tree is 0
return 0;
}
// Height of tree is 1 + maximum of height of left or right subtree
return 1 + Math.max(height(root.left), height(root.right));
}

// Function to check if given tree is balanced or not
private static boolean isBalanced(Node root) {
if (root == null) {
// Empty tree is always balanced
return true;
}

// Find the left subtree height and right subtree height
int leftHeight = height(root.left);
int rightHeight = height(root.right);

// If this node is balanced and also its left and right subtree are balanced return true
// else return false
return (Math.abs(leftHeight - rightHeight) <= 1) && isBalanced(root.left)
&& isBalanced(root.right);
}

public static void main(String[] args) {
// Tree in example 1
Node root = new Node(18);
root.left = new Node(4);
root.right = new Node(20);
root.right.left = new Node(13);
root.right.right = new Node(70);

System.out.println(isBalanced(root));

// Tree in example 2
Node root2 = new Node(3);
root2.left = new Node(4);
root2.right = new Node(8);
root2.left.left = new Node(5);
root2.left.right = new Node(9);
root2.right.right = new Node(7);
root2.right.right.left = new Node(6);

System.out.println(isBalanced(root2));
}
}```

### C ++代碼

```#include <iostream>
using namespace std;

class Node {
public:
int data;
Node *left;
Node *right;
};

// Function to calculate height of a tree rooted at root
int height(Node *root) {
if (root == NULL) {
// Height of empty tree is 0
return 0;
}
// Height of tree is 1 + maximum of height of left or right subtree
return 1 + std::max(height(root->left), height(root->right));
}

// Function to check if given tree is balanced or not
bool isBalanced(Node *root) {
if (root == NULL) {
// Empty tree is always balanced
return true;
}

// Find the left subtree height and right subtree height
int leftHeight = height(root->left);
int rightHeight = height(root->right);

// If this node is balanced and also its left and right subtree are alanced return true
// else return false
return (abs(leftHeight - rightHeight) <= 1) && isBalanced(root->left)
&& isBalanced(root->right);
}

// Function to allocate new memory to a tree node
Node* newNode(int data) {
Node *node = new Node();
node->data = data;
node->left = NULL;
node->right = NULL;

return (node);
}

int main() {
// Tree in example 1
Node *root = newNode(18);
root->left = newNode(4);
root->right = newNode(20);
root->right->left = newNode(13);
root->right->right = newNode(70);

if (isBalanced(root) == true) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}

// Tree in example 2
Node* root2 = newNode(3);
root2->left = newNode(4);
root2->right = newNode(8);
root2->left->left = newNode(5);
root2->left->right = newNode(9);
root2->right->right = newNode(7);
root2->right->right->left = newNode(6);

if (isBalanced(root2) == true) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
return 0;
}```
```true
false```

## 平衡二叉樹的優化方法

1. 空樹始終遵循高度平衡（基本情況）。
2. 通過遞歸調用height函數來找到左側的高度，如果height為-1，則左子樹不平衡，請立即返回-1。
3. 通過遞歸調用height函數來找到合適的高度，如果height為-1，則右邊的子樹是不平衡的，立即返回-1。
4. 如果左右高度之差小於或等於1，則返回height（1 + max（leftHeight，rightHeight），否則返回-1。

### JAVA代碼

```public class BalancedBinaryTree {
static class Node {
int data;
Node left;
Node right;

public Node(int data) {
this.data = data;
left = right = null;
}
}

// Modified height function
// Returns the height of tree if the tree is balanced and returns -1 is the tree is not balanced
private static int height(Node root) {
if (root == null) {
// Empty tree is always balanced
return 0;
}

// Find the left height
int lh = height(root.left);
if (lh == -1) {
// Left subtree is unbalanced
return -1;
}
// Find the right height
int rh = height(root.right);
if (rh == -1) {
// Right subtree is unbalanced
return -1;
}
if (Math.abs(lh - rh) <= 1) {
// Balanced tree, return the height
return Math.max(lh, rh) + 1;
}
// Unbalanced tree
return -1;
}

private static boolean isBalanced(Node root) {
// Call the modified height function
int height = height(root);
if (height == -1) {
// Unbalanced tree
return false;
}
// Balanced tree
return true;
}

public static void main(String[] args) {
// Tree in example 1
Node root = new Node(18);
root.left = new Node(4);
root.right = new Node(20);
root.right.left = new Node(13);
root.right.right = new Node(70);

System.out.println(isBalanced(root));

// Tree in example 2
Node root2 = new Node(3);
root2.left = new Node(4);
root2.right = new Node(8);
root2.left.left = new Node(5);
root2.left.right = new Node(9);
root2.right.right = new Node(7);
root2.right.right.left = new Node(6);

System.out.println(isBalanced(root2));
}
}```

### C ++代碼

```#include <iostream>
using namespace std;

class Node {
public:
int data;
Node *left;
Node *right;
};

// Function to calculate height of a tree rooted at root
int height(Node *root) {
if (root == NULL) {
// Empty tree is always balanced
return 0;
}
// Find the left height
int lh = height(root->left);
if (lh == -1) {
// Left subtree is unbalanced
return -1;
}
// Find the right height
int rh = height(root->right);
if (rh == -1) {
// Right subtree is unbalanced
return -1;
}
if (abs(lh - rh) <= 1) {
// Balanced tree, return the height
return 1 + std::max(height(root->left), height(root->right));
}
// Unbalanced tree
return -1;
}

// Function to check if given tree is balanced or not
bool isBalanced(Node *root) {
// Call the modified height function
int h = height(root);
if (h == -1) {
// Unbalanced tree
return false;
}
// Balanced tree
return true;
}

// Function to allocate new memory to a tree node
Node* newNode(int data) {
Node *node = new Node();
node->data = data;
node->left = NULL;
node->right = NULL;

return (node);
}

int main() {
// Tree in example 1
Node *root = newNode(18);
root->left = newNode(4);
root->right = newNode(20);
root->right->left = newNode(13);
root->right->right = newNode(70);

if (isBalanced(root) == true) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}

// Tree in example 2
Node* root2 = newNode(3);
root2->left = newNode(4);
root2->right = newNode(8);
root2->left->left = newNode(5);
root2->left->right = newNode(9);
root2->right->right = newNode(7);
root2->right->right->left = newNode(6);

if (isBalanced(root2) == true) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
return 0;
}```
```true
false```