算法练习篇之：平衡二叉树

题目描述

平衡二叉树
要求：输入一棵二叉树，判断该二叉树是否是平衡二叉树。

解题思路

平衡二叉树：它是一棵空树，或者它的左右子树的高度差不超过1，同时它的左右子树为一棵二叉树。而衡量树和平衡因子说的就是左右子树的高度差，可以为0,1,-1。
综上所述，平衡二叉树须具备的条件为：
1.左子树是平衡二叉树
2.右子树是平衡二叉树
3.左右子树的高度之差 <= 1
这三点也是我们判断的依据，而其中求二叉树的深度，我们之前也已经专门有一篇讲过了，在判断左右子树是否为平衡二叉树上，依旧采用递归的思想。

图示

二叉树结构：

代码实现

去博客设置页面，选择一款你喜欢的代码片高亮样式，下面展示同样高亮的 代码片.

class TreeNode{  //定义二叉树的节点
    TreeNode father;
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(TreeNode left,TreeNode right){
        this.left=left;
        this.right=right;
    }
    TreeNode(int val){
        this.val=val;
    }
    TreeNode(){}
}

public class balanceTree {
    //平衡二叉树
    public boolean isBalance(TreeNode root){
        if (root==null){
            return true;
        }
        int leftDepth=treeDepth(root.left);
        int rightDepth=treeDepth(root.right);

        return (Math.abs(leftDepth-rightDepth)<=1&&isBalance(root.left)&&isBalance(root.right));

    }
    private int treeDepth(TreeNode pRoot){//求二叉树深度
        if (pRoot==null){
            return 0;
        }

        int left=treeDepth(pRoot.left);
        int right=treeDepth(pRoot.right);

        return Math.max(left,right)+1;

    }
    public static void main(String[] args) {
        TreeNode nodeA = new TreeNode();
        TreeNode nodeB = new TreeNode();
        TreeNode nodeC = new TreeNode();

        nodeA.left = nodeB;
        nodeA.right = nodeC;
        nodeA.val = 1;
        nodeB.left = null;
        nodeB.right = null;
        nodeB.val = 2;
        nodeC.left = null;
        nodeC.right = null;
        nodeC.val = 3;


        balanceTree test=new balanceTree();
        boolean is=test.isBalance(nodeA);
        System.out.println(is);
    }
}

总结

本题来源于面试经典教材《剑指offer》中 归属于二叉树类型题目。
同许多在算法道路上不断前行的人一样，不断练习，修炼自己！
如有博客中存在的疑问或者建议，可以在下方留言一起交流，感谢各位！
最后，感谢Jerry算法！

国庆出去浪了五天，昨天晚上回来贼困，今天一觉睡到上午11点多，起来写两篇博客！！！还需要调整下状态，有点懵！ 五天逛吃逛吃胖了好几斤。。。。