Java算法题-解析 判断二叉树是否为平衡二叉树 算法问题

题目：

给定一个二叉树，判断它是否是高度平衡的二叉树。

引言：

平衡二叉树是一种特殊的二叉树，它的高度差不超过1，这使得树的查找和插入操作的时间复杂度保持在O(log n)的水平。因此，判断一个二叉树是否为平衡二叉树对于优化树的性能非常重要。

判断一个二叉树是否为平衡二叉树的核心问题在于计算每个节点的左子树高度和右子树高度，然后检查它们之间的差是否超过1。

算法思路：

1. 定义一个递归函数 isBalanced，该函数接受一个二叉树节点作为参数，并返回该节点的高度（或者-1表示不平衡）。
2. 在每个节点上，递归调用 isBalanced 函数来计算左子树的高度和右子树的高度。
3. 如果左子树或右子树不平衡，或者它们的高度差超过1，则返回-1，表示整棵树不平衡。
4. 否则，返回左子树和右子树的较大高度加1作为当前节点的高度。
5. 在递归的过程中，如果任何节点返回-1，则整棵树都不平衡，否则它是平衡二叉树。

代码实现：

以下是使用 Java 实现的解决方案：

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

public class BalancedBinaryTree {
    public boolean isBalanced(TreeNode root) {
        return checkBalance(root) != -1;
    }

    private int checkBalance(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int leftHeight = checkBalance(node.left);
        if (leftHeight == -1) {
            return -1;
        }

        int rightHeight = checkBalance(node.right);
        if (rightHeight == -1) {
            return -1;
        }

        if (Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        }

        return Math.max(leftHeight, rightHeight) + 1;
    }

    public static void main(String[] args) {
        BalancedBinaryTree solution = new BalancedBinaryTree();

        // 创建一个示例二叉树
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);

        boolean isBalanced = solution.isBalanced(root);
        System.out.println("是否为平衡二叉树: " + isBalanced);
    }
}

算法分析：

• 时间复杂度：对于每个节点，我们只需遍历一次，因此时间复杂度是O(n)，其中n是二叉树的节点数。
• 空间复杂度：递归调用栈的深度最多为树的高度，所以空间复杂度是O(log n)。

示例和测试：

假设给定一个示例二叉树 root，如下所示：

     3
    / \
   9  20
     /  \
    15   7

根据算法，我们可以判断这棵树是平衡二叉树。我们可以使用以下代码进行测试：

public class Main {
    public static void main(String[] args) {
        BalancedBinaryTree solution = new BalancedBinaryTree();

        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);

        boolean isBalanced = solution.isBalanced(root);
        System.out.println("是否为平衡二叉树: " + isBalanced);
    }
}

总结：

判断一个二叉树是否为平衡二叉树是一个常见的问题，使用递归的方式计算每个节点的左子树高度和右子树高度，然后判断它们之间的差是否超过1，可以有效地解决这个问题。这个算法的时间复杂度是O(n)，空间复杂度是O(log n)，其中n是二叉树的节点数。解决这个问题有助于理解二叉树的平衡性质，以及如何使用递归来处理树结构。