你知道代码如何实现判断是否是平衡二叉树吗?下面要给大家分享就是具体的代码实现和思路。

题目：

输入一棵二叉树，判断这个二叉树是否是平衡二叉树。

思路1

代码实现：

public class Solution
{
    public int cheat(TreeNode root)
    {
        if (root == null) return 0;
        int left = cheat(root.left);
        int right = cheat(root.right);
        return (left >= 0 && right >= 0 && Math.abs(left - right) <= 1) ? 1 + Math.max(left, right) : -1;
    }
    public boolean IsBalanced_Solution(TreeNode root)
    {
        return cheat(root) >= 0;
    }
}

思路2

代码实现：

public class Solution
{
    public boolean IsBalanced_Solution(TreeNode root)
    {
        if (root == null) return true;
        int leftDepth = getDepth(root.left);
        int rightDepth = getDepth(root.right);
        if (Math.abs(leftDepth - rightDepth) > 1) return false;
        return (IsBalanced_Solution(root.left) && IsBalanced_Solution(root.left));
    }
    private int getDepth(TreeNode root)
    {
        if (root == null) return 0;
        int leftDepth = 1 + getDepth(root.left);
        int rightDepth = 1 + getDepth(root.right);
        return leftDepth > rightDepth ? leftDepth : rightDepth;
    }
}

思路3：

最直接的做法，遍历每个结点，借助一个获取树深度的递归函数，依据这个结点的左右子树高度差判断是否平衡，然后递归地对左右子树进行判断。

代码实现：

public classSolution
{
    public boolean IsBalanced_Solution(TreeNode root)
    {
        if (root == null)
        {
            return true;
        }
        return Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1 &&
            IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
    }
    private int maxDepth(TreeNode root)
    {
        if (root == null)
        {
            return 0;
        }
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }
}

判断平衡二叉树的实现大家都了解了吗?请继续关注本站，有更多的Java实例可以和大家分享。