二叉树 | 二叉树的对称问题

题目描述

给定一棵二叉树，判断它是否是自身的镜像（即是否对称）。

解题思路

对称的二叉树具有以下特点：

1. 根节点的左子树和右子树是镜像对称的。
2. 左子树的右子树和右子树的左子树是镜像对称的。

我们可以使用递归来判断二叉树是否对称。递归的思路是比较左子树的左节点和右子树的右节点，以及左子树的右节点和右子树的左节点是否相等, 同时需要考虑左子树与右子树不等长的问题.

java代码示例

public class SymmetricBinaryTree {
    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);
    }
}

当递归判断左右子树是否对称时，我们需要考虑到左右子树的长度可能不等，因此在递归的过程中，需要加入条件判断来提前发现不对称的情况。具体来说，我们在判断的过程中，添加以下条件：

if (left == null || right == null) {
    return false;
}

这个条件的意义在于：

1. 如果左子树 left 为空而右子树 right 不为空，或者右子树 right 为空而左子树 left 不为空，这两种情况下，左右子树不对称，我们可以直接返回 false。
2. 如果左右子树同时为空，说明当前节点是对称的，可以返回 true。
3. 如果左右子树都不为空，继续递归判断左右子树的镜像对称性。

这样的条件判断提前终止递归，避免了不必要的计算，提高了程序的效率。在代码实现中，这部分的判断通过 if (left == null || right == null) 实现。希望这一解释能够帮助你更好地理解这段代码。

单元测试

import org.junit.Test;
import static org.junit.Assert.*;

public class SymmetricBinaryTreeTest {

    @Test
    public void testIsSymmetric() {
        SymmetricBinaryTree symmetricTree = new SymmetricBinaryTree();

        // Example 1: Symmetric tree
        //     1
        //    / \
        //   2   2
        //  / \ / \
        // 3  4 4  3
        TreeNode symmetricRoot = new TreeNode(1);
        symmetricRoot.left = new TreeNode(2);
        symmetricRoot.right = new TreeNode(2);
        symmetricRoot.left.left = new TreeNode(3);
        symmetricRoot.left.right = new TreeNode(4);
        symmetricRoot.right.left = new TreeNode(4);
        symmetricRoot.right.right = new TreeNode(3);

        assertTrue(symmetricTree.isSymmetric(symmetricRoot));

        // Example 2: Non-symmetric tree
        //     1
        //    / \
        //   2   2
        //    \   \
        //     3   3
        TreeNode nonSymmetricRoot = new TreeNode(1);
        nonSymmetricRoot.left = new TreeNode(2);
        nonSymmetricRoot.right = new TreeNode(2);
        nonSymmetricRoot.left.right = new TreeNode(3);
        nonSymmetricRoot.right.right = new TreeNode(3);

        assertFalse(symmetricTree.isSymmetric(nonSymmetricRoot));
    }
}