美文网首页
判断一个树是否为平衡二叉树

判断一个树是否为平衡二叉树

作者: 霍运浩 | 来源:发表于2019-04-18 21:28 被阅读0次

    1 什么是平衡二叉树?

    左子树和右子树的高度不能超过1 的书就叫平衡二叉树。

    2 解题思路

    先序遍历 ,获取左子树的高度和 获取右子树的高度 然后比较高度差 ,如何高度大于1 返回flase,否则返回true,并递归该过程。

    3 代码实现

    /**
     * 判断一个树是否为平衡二叉树
     * @author Administrator
     *
     */
    public class Code_06_IsBalancedTree {
    
        public static class Node {
            public int value;
            public Node left;
            public Node right;
    
            public Node(int data) {
                this.value = data;
            }
        }
    
        public static boolean isBalance(Node head) {
            boolean[] res = new boolean[1];
            res[0] = true;
            getHeight(head, 1, res);
            return res[0];
        }
        /**
         * 先序遍历  平衡二叉树 左右子树高度相差不超过1
         * @param head
         * @param level
         * @param res
         * @return
         */
        public static int getHeight(Node head, int level, boolean[] res) {
            if (head == null) {
                return level;
            }
            int lH = getHeight(head.left, level + 1, res);//左子树的高度
            if (!res[0]) {
                return level;
            }
            int rH = getHeight(head.right, level + 1, res);//右子树高度
            if (!res[0]) {
                return level;
            }
            if (Math.abs(lH - rH) > 1) {//左右子树高度差值
                res[0] = false;
            }
            return Math.max(lH, rH);
        }
    
        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(isBalance(head));
    
        }
    
    }
    
    

    相关文章

      网友评论

          本文标题:判断一个树是否为平衡二叉树

          本文链接:https://www.haomeiwen.com/subject/sxyxgqtx.html