Java算法题-解析 "对称二叉树" 算法问题

题目：

给定一个二叉树，检查它是否是自身的镜像（即，围绕其中心对称）。

引言：

"对称二叉树" 算法问题是一个关于二叉树遍历和比较的问题。解决这个问题需要对二叉树的结构和节点值的比较有一定的理解，同时需要找到一种方法来判断二叉树是否是对称的。通过解答这个问题，我们可以提升对二叉树和遍历的考虑，同时也能拓展对问题求解的能力。

算法思路：

为了判断一个二叉树是否对称，我们可以使用递归的方法进行比较。具体思路如下：

1. 首先检查根节点是否为 null，如果是，则认为是对称的。
2. 否则，比较根节点的左子树和右子树，判断它们是否对称。
3. 对比左子树的左子树和右子树的右子树，以及左子树的右子树和右子树的左子树，递归判断它们是否对称。

代码实现：

以下是使用 Java 实现的 "对称二叉树" 算法的示例代码：

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

public class SymmetricTree {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isMirror(root.left, root.right);
    }

    private boolean isMirror(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        }
        if (left == null || right == null) {
            return false;
        }
        return (left.val == right.val) && isMirror(left.left, right.right) && isMirror(left.right, right.left);
    }

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

        // Create a sample symmetric binary tree
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(4);
        root.right.right = new TreeNode(3);

        boolean isSymmetric = solution.isSymmetric(root);

        System.out.println("Is the binary tree symmetric: " + isSymmetric);
    }
}

算法分析：

• 时间复杂度：每个节点都会被访问一次，所以时间复杂度为 O(n)，其中 n 是节点的数量。
• 空间复杂度：递归栈的深度为树的高度，所以空间复杂度为 O(h)，其中 h 是树的高度。

示例和测试：

假设给定一个对称的二叉树如下：

        1
       / \
      2   2
     / \ / \
    3  4 4  3

根据算法，判断这棵二叉树是否对称，结果为 true。

我们可以使用以下代码进行测试：

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

        // Create a sample symmetric binary tree
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(4);
        root.right.right = new TreeNode(3);

        boolean isSymmetric = solution.isSymmetric(root);

        System.out.println("Is the binary tree symmetric: " + isSymmetric);
    }
}

总结：

"对称二叉树" 算法题要求判断给定的二叉树是否对称，是一个关于二叉树的遍历和比较的问题。通过实现这个算法，我们可以提升对二叉树和遍历的考虑，同时也能拓展对问题求解的能力。这个问题利用递归的思路，比较二叉树的左子树和右子树是否对称。