判断一棵二叉树是否是平衡二叉树:

12.判断一棵二叉树是否是平衡二叉树(JavaScript版) 算法 第1张
<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>
<body>
    <script>
        //二叉平衡搜索树:
        //1.根节点的左子树与右子树的高度差不能超过1
        //2.这棵二叉树的每个子树都符合第一条

        function Node(value){
            this.value = value;
            this.left = null;
            this.right = null;
        }

        var nodeA = new Node("a");
        var nodeB = new Node("b");
        var nodeC = new Node("c");
        var nodeD = new Node("d");
        var nodeE = new Node("e");
        var nodeF = new Node("f");
        var nodeG = new Node("g");

        nodeA.left = nodeB;
        nodeA.right = nodeC;
        nodeB.left = nodeD;
        nodeB.right = nodeE;
        nodeC.left = nodeF;
        nodeC.right = nodeG;

        //判断二叉树是否平衡
        function isBalance(root){
            if(root == null) return true;
            //获取左右的深度
            var leftDeep = getDeep(root.left);
            var rightDeep = getDeep(root.right);
            //若左右深度相差大于1,则不是平衡树
            if(Math.abs(leftDeep - rightDeep) > 1){
                return false;
            }else{
                //判断左右子树是否平衡
                return isBalance(root.left) && isBalance(root.right);
            }
        }

        //获取树的深度
        function getDeep(root){
            if(root == null) return 0;
            var leftDeep = getDeep(root.left);
            var rightDeep = getDeep(root.right);
            return Math.max(leftDeep, rightDeep) + 1;//取两个深度中最大的一个,加上自身
        }

        console.log(isBalance(nodeA));
    </script>
</body>
</html>
判断平衡二叉树

 

SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。
扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄