39.平衡二叉树

题目描述：

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

3<br />   / \<br />  9  20<br />    /  \<br />   15   7<br />返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

   1<br />      / \<br />     2   2<br />    / \<br />   3   3<br />  / \<br /> 4   4<br />返回 false 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof

知识点：

• 深度优先遍历

解题思路：

• 这道题目要求判断一棵树是否为平衡二叉树，平衡二叉树的条件为其每一个节点的左右子树的最大深度小于1
• 对于关于二叉树深度的题我们优先想到的便是深度优先遍历，我们每递归便要判断一次最大深度是否大于1
• 递归的返回条件为如果不存在我返回0，每次返回左右子树中深度最深的

解题代码：

function IsBalanced_Solution(pRoot)
{
    // write code here
    if(!pRoot) {
        return true;
    }
    let res = true;
    const dfs = (node) => {
        if(!node) return 0;
        let left = dfs(node.left) + 1;
        let right = dfs(node.right) + 1;
        if(Math.abs(left - right) > 1) {
            res = false;
        }
        return Math.max(left,right);
    }
    dfs(pRoot);
    return res;
}