前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >判断树是不是平衡二叉树

判断树是不是平衡二叉树

作者头像
名字是乱打的
发布2022-05-13 09:50:18
2280
发布2022-05-13 09:50:18
举报
文章被收录于专栏:软件工程

平衡二叉树定义:它或者是一颗空树,或者具有以下性质的二叉排序树: 它的左子树和右子树的深度之差(平衡因子)的绝对值不超过1 且它的左子树和右子树都是一颗平衡二叉树。

关键思想: 递归遍历每个结点的左右树 若左树或者右树不是平衡二叉树则该结点树也不少平衡二叉树 若左树或者右树都是平衡二叉树则判断左右树高度之差,如果高度差大于1也是不平衡二叉树,否则该结点是平衡二叉树,高度是左右子树中较大值+1

代码
代码语言:javascript
复制
package com.algorithm.practice.tree;

public class BalanceTreeJudge {  //定义树
    public static class Node {
        public int value;
        public Node left;
        public Node right;
        public Node parent;

        public Node(int data) {
            this.value = data;
        }
    }

    public static class returnData { //定义返回值包装类
        boolean isB;
        int h;
        public returnData(boolean isB, int h) {
            this.isB = isB;
            this.h = h;
        }
    }
    public static  returnData Judge(Node head){ //递归判断左右子树
        if (head==null){
            return new returnData(true,0);
        }
        if (!Judge(head.left).isB){ //如果左树不平衡
            return new returnData(false,0); //如果其左树不平衡,这里高度无所谓了
        }
        if (!Judge(head.right).isB){//如果右树不平衡
            return new returnData(false,0);//如果其右树不平衡,这里高度无所谓了
    }
        if (Math.abs(Judge(head.left).h-Judge(head.right).h)>1){//若两者高度差的绝对值
        return new returnData(false,0);
    }
        //如果前面的判断非平衡二叉树都没拦截到,则该子树是平衡二叉树,该结点高度是左右子树高度较大值+1
        return new returnData(true,Math.max(Judge(head.left).h,Judge(head.right).h)+1);
    }
    public static void main(String[] args) {
        Node head = new Node(1);
        head.left = new Node(2);
        head.right = new Node(3);
        head.left.left = new Node(4);
        head.left.right = new Node(5);
        head.right.left = new Node(6);
        head.right.right = new Node(7);
        System.out.println(Judge(head).isB);
    }
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2022-05-13,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 代码
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档