###### tags: `Leetcode` `easy` `tree` `python` `c++`

# 110. Balanced Binary Tree

## [題目出處:] https://leetcode.com/problems/balanced-binary-tree/

## 題目:
Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

**a binary tree in which the left and right subtrees of every node differ in height by no more than 1.**

## 解題思路:
1. DFS求左右子的heights逐一進行比較: O(NlogN) 慢
2. 設balanced在遞迴左右子點時，隨時判斷是否仍平衡 : O(N)

## Python ( O(NlongN) ):

class Solution(object):
    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True
        else:
            ans = abs(self.depth(root.left)-self.depth(root.right))
            if ans <= 1:
                return self.isBalanced(root.left) and self.isBalanced(root.right)
        return False
            
    def depth(self,root):
        if not root or root.val == None:
            return 0
        else:
            return max(self.depth(root.left),self.depth(root.right))+1

## Python ( O(N) ):

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
    def insertLeft(self,node):
        if self.left==None:
            self.left=TreeNode(node)
        else:
            self.left.insertLeft(node)
    def insertRight(self,node):
        if self.right==None:
            self.right=TreeNode(node)
        else:
            self.right.insertRight(node)
    def printTree(self):
        root=self
        stack=[root]
        res=[]
        while stack:
            root=stack.pop(0)
            res.append(root.val)
            if root.left:
                stack.append(root.left)
            if root.right:
                stack.append(root.right)
        print(res)

class Solution(object):
    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        # O(NlogN) for dfs and get each height
        #O(n) for this 
        self.balance=True
        self.height(root)
        return self.balance
    def height(self,root):
        if not root:
            return 0
        hL=self.height(root.left)
        hR=self.height(root.right)
        if abs(hL-hR)>1:
            self.balance=False
            return -1
        return max(hL,hR)+1

root=TreeNode(3)
root.insertLeft(9)
root.insertRight(20)
root.right.insertLeft(15)
root.right.insertRight(7)
root.printTree()
result=Solution()
ans=result.isBalanced(root)
print(ans)

## C++:

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

struct TreeNode{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(): val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right): val(x), left(left), right(right) {}
};

void InsertLeft(TreeNode* root, int data){
    TreeNode *tmp=root;
    if (tmp->left != nullptr)
        InsertLeft(root->left, data);
    else{
        TreeNode *new_left= new TreeNode(data);
        tmp->left=new_left;
    }
}

void InsertRight(TreeNode*root, int data){
    TreeNode *tmp=root;
    if (tmp->right != nullptr)
        InsertRight(root->right, data);
    else{
        TreeNode *new_right= new TreeNode(data);
        tmp->right=new_right;
    }
}

void PrintTree(TreeNode* root){
    TreeNode *tmp=root;
    vector<int> res;
    queue<TreeNode*> que;
    que.push(root);
    while (!que.empty()){
        TreeNode *curRoot=que.front(); que.pop();
        res.push_back(curRoot->val);
        if (curRoot->left)
            que.push(curRoot->left);
        if (curRoot->right)
            que.push(curRoot->right);
    }
    for (int i=0; i<res.size(); i++){
        cout<<res[i]<<" ";
    }
    cout<<endl;
}

class Solution{
public:
    bool isBalanced(TreeNode* root){
        if(root==nullptr)
            return true;
        bool balanced=true;
        height(root, &balanced);
        return balanced;
    }
    bool height(TreeNode* root, bool* balanced){
        if (!root)
            return 0;
        int hL=height(root->left, balanced);
        int hR=height(root->right,balanced);
        if (abs(hL-hR)>1){
            //call by reference get real value
            *balanced=false;
            return -1;
        }
        return max(hL,hR)+1;
    }
};

int main(){
    TreeNode *root= new TreeNode(3);
    InsertLeft(root,9);
    InsertRight(root,20);
    InsertLeft(root->right,15);
    InsertRight(root->right,7);
    PrintTree(root);

    Solution res;
    bool ans=res.isBalanced(root);
    cout<<ans<<endl;
    return 0;
}