判断树是不是平衡二叉树

平衡二叉树定义:它或者是一颗空树，或者具有以下性质的二叉排序树： 它的左子树和右子树的深度之差(平衡因子)的绝对值不超过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);
    }
}

二叉树

0 人点赞