子树问题：判断子树与对称性

这类题目的核心是"两棵树的同步比较"，掌握双指针递归思路即可覆盖所有变体。

对称二叉树（LeetCode 101）

判断一棵树是否镜像对称。

public boolean isSymmetric(TreeNode root) {
    return check(root.left, root.right);
}

private boolean check(TreeNode l, TreeNode r) {
    if (l == null && r == null) return true;
    if (l == null || r == null) return false;
    return l.val == r.val
        && check(l.left,  r.right)  // 镜像：左的左 vs 右的右
        && check(l.right, r.left);  // 镜像：左的右 vs 右的左
}

相同的树（LeetCode 100）

判断两棵树是否完全相同（结构和值均相同）。

public boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) return true;
    if (p == null || q == null) return false;
    return p.val == q.val
        && isSameTree(p.left, q.left)
        && isSameTree(p.right, q.right);
}

与对称树的区别：相同树用 (l.left, r.left) 和 (l.right, r.right)，对称树用镜像配对。

另一棵树的子树（LeetCode 572）

判断 subRoot 是否是 root 的子树（结构和值完全匹配）。

public boolean isSubtree(TreeNode root, TreeNode subRoot) {
    if (root == null) return false;
    return isSameTree(root, subRoot)
        || isSubtree(root.left, subRoot)
        || isSubtree(root.right, subRoot);
}

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

时间：O(m × n)，可用字符串序列化 + KMP 优化到 O(m + n)。

翻转等价二叉树（LeetCode 951）

允许对任意节点的子树做翻转，判断两棵树是否能变得相同。

public boolean flipEquiv(TreeNode root1, TreeNode root2) {
    if (root1 == null && root2 == null) return true;
    if (root1 == null || root2 == null) return false;
    if (root1.val != root2.val) return false;
    // 两种情况：不翻转，or 翻转
    boolean noFlip = flipEquiv(root1.left, root2.left)   && flipEquiv(root1.right, root2.right);
    boolean flip   = flipEquiv(root1.left, root2.right)  && flipEquiv(root1.right, root2.left);
    return noFlip || flip;
}

二叉树的镜像（剑指 Offer 27 / LeetCode 226）

与翻转二叉树相同（前面已讲，此处补充迭代版本）：

public TreeNode mirrorTree(TreeNode root) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    if (root != null) stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        if (node.left  != null) stack.push(node.left);
        if (node.right != null) stack.push(node.right);
        // 交换左右子节点
        TreeNode tmp = node.left;
        node.left  = node.right;
        node.right = tmp;
    }
    return root;
}

总结