# 110. Balanced Binary Tree
###### tags: `LeetCode`
## **Link**
https://leetcode.com/problems/balanced-binary-tree/

## **Code**

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    // 樹裡面放什麼數字完全不重要
    int dfs(TreeNode* root, bool &ans)
    {
        int lf=0,ri=0; // 存左右深度
        if(root->left!=nullptr) // 左邊有路就往下走
            lf=dfs(root->left,ans); // 回傳左邊最深深度
        if(root->right!=nullptr) // 右邊有路就往下走
            ri=dfs(root->right,ans); // 回傳右邊最深深度
        if(abs(lf-ri)>1) // 深度差大於1就不合題目規定
            ans=false;
        return max(lf,ri)+1; // 回傳比較深的那邊
    }

    bool isBalanced(TreeNode* root) 
    {
        bool ans=true; // 預設為合法樹
        if(root!=nullptr) // 防止空白測資爆掉
            dfs(root,ans); // 遞迴，用call by reference傳答案
        return ans;
    }
};

## date
**2023.01.20**

{%hackmd @nnks8908/background_leetcode %}