判断是不是平衡二叉树

[编程题]判断是不是平衡二叉树

热度指数：544473 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。

在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树

平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

样例解释：

样例二叉树如图，为一颗平衡二叉树

注：我们约定空树是平衡二叉树。

数据范围： $n \le 100$ ,树上节点的val值满足 $0 \le n \le 1000$

要求：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

输入描述:

输入一棵二叉树的根节点

输出描述:

输出一个布尔类型的值

示例1

输入

{1,2,3,4,5,6,7}

输出

true

示例2

输入

{}

输出

true

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

查看答案及解析

JavaScript Node

ch橙子🍊

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */

function IsBalanced_Solution(pRoot)
{
    // write code here
    function func(pRoot){
    if(!pRoot){
            return [true,0]
        }else{
                let [flag1,len1]=func(pRoot.left)
                let [flag2,len2]=func(pRoot.right)
                return [Math.abs(len1-len2)<=1&&flag1&&flag2,Math.max(len1+1,len2+1)];
        } 
    }
    return func(pRoot)[0];
}
    
   
module.exports = {
    IsBalanced_Solution : IsBalanced_Solution
};

发表于 2022-12-11 15:18:07 回复(0)

JavaScript Node

牛客67815066号

简洁的JavaScript:

function IsBalanced_Solution(pRoot)
{
    // write code here
    if (pRoot === null) return 1;
    
    let left = IsBalanced_Solution(pRoot.left);
    if (!left) return 0;
    
    let right = IsBalanced_Solution(pRoot.right);
    if (!right) return 0;
    
    return Math.abs(right - left) <= 1 && Math.max(left, right) + 1
}

发表于 2021-10-09 05:09:13 回复(0)

JavaScript Node

小夏不饿

function IsBalanced_Solution(pRoot)
{
    if(pRoot === null){
        return true;
    }
//     左右子树的高度绝对值相差大于1，则不是平衡二叉树
    if(Math.abs(depth(pRoot.left) - depth(pRoot.right)) > 1) return false;
//     进一步判断左右子树是否为平衡二叉树
    return IsBalanced_Solution(pRoot.left) && IsBalanced_Solution(pRoot.right);
}

// 求二叉树的深度
function depth(node){
    if(node === null){
        return 0;
    }
    let left = depth(node.left);
    let right = depth(node.right);
    return Math.max(left,right) + 1;
}

发表于 2021-10-01 17:19:13 回复(0)