如何实现判断是否是平衡二叉树?实现和思路

KLQ 2020-04-15 16:02:26 java常见问答 3256

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

题目:

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

思路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实例可以和大家分享。