Check if Two Binary Trees Are Mirror in Java

比较两棵二叉树的结构和节点值，以检查它们是否镜像。一棵二叉树是另一棵二叉树的镜像，如果其中一棵的左子树与另一棵的右子树匹配，反之亦然。这涉及到递归来系统地遍历和比较相应的节点。

示例

输入

树 1

树 2

输出：这两棵树是彼此的镜像。

解释

这两棵树是镜像的，因为它们的根节点相同，树 1 的左子树与树 2 的右子树匹配，而树 1 的右子树与树 2 的左子树匹配。这种对称性适用于所有相应的节点，证实它们是镜像的。

方法 1：递归树遍历方法

算法

步骤 1：基本条件（两棵树都为 null）：如果两棵树都为 null，则认为它们是镜像的，因为它们的结构（空）和值（无）都相同。

示例：两棵空树永远是镜像的。返回 true。

步骤 1.1：检查单节点树：如果两棵树都只包含一个节点（没有子节点），则比较它们的值。

如果值相等，则树是镜像的，因为它们的结构和值匹配。

如果值不同，则树不是镜像的。

步骤 2：基本条件（一棵树为 null）：如果一棵树为 null 而另一棵不为 null，则它们不可能是镜像。这是因为一棵树有节点而另一棵树没有，打破了它们成为镜像所需的对称性。在这种情况下，返回 false。

步骤 2.1：检查不匹配的子树结构

如果一棵树有左子节点或右子节点，而另一棵树中的相应子树为 null，则它们不可能是镜像。例如，如果树 1 有左子节点但树 2 的右子节点为 null，则它们的结构不同，打破了对称性。在这种情况下，返回 false。

步骤 3：比较根节点：检查两棵树的根节点的值是否相同。如果不相同，则树不可能是镜像，因此返回 false。

示例

树 1 根节点：4，树 2 根节点：4 → 继续下一步。

树 1 根节点：4，树 2 根节点：5 → 返回 false。

步骤 3.1：递归检查子树：递归比较

1. 第一棵树的左子树与第二棵树的右子树。
2. 第一棵树的右子树与第二棵树的左子树。

此步骤可确保结构和节点值以镜像方式匹配。

步骤 4：组合递归结果：如果所有递归调用都返回 true，则两棵树是镜像的。为了使树保持对称性，左-右和右-左子树的比较在每个级别都必须得到满足。

步骤 4.1：检查两个子树的递归结果：在递归比较子树之后，确保左-右和右-左的比较都返回 true。如果任一比较失败，则树不可能是镜像。此步骤验证对称性在每个级别都得到维持，确保每一对相应的子树在结构和值方面都正确对齐。

步骤 5：返回最终结果：遍历完树的所有级别后，如果所有比较都匹配，则返回 true；否则，返回 false。

步骤 6：处理边缘情况：完成递归并返回最终结果后，请确保已正确处理任何边缘情况，例如深度不均或节点值不同的树。仔细检查在遍历过程中可能被忽略的结构或节点比较中的潜在差异。如果所有条件都满足，则确认树是镜像的。

输出

 
True   

复杂度分析

时间复杂度

检查两棵 二叉 树是否为镜像的时间复杂度为 O(n)，其中 n 是节点总数。这是因为在递归遍历期间，每个节点都会被访问一次。每个节点的比较和递归操作都需要恒定的时间，从而产生线性复杂度。

空间复杂度

检查两棵二叉树是否为镜像的空间复杂度为 O(h)，其中 h 是树的高度。这是由于递归函数调用使用了与树高成比例的堆栈空间。在最坏情况下，对于倾斜树，其复杂度会达到 O(n)。

方法 2：使用堆栈的迭代方法

算法

步骤 1：处理边缘情况（两棵树都为空）：如果两棵树都为 null，则它们明显是彼此的镜像，因为没有需要比较的内容。在这种情况下，返回 true。

一棵树为空：如果只有一棵树为 null，则另一棵树不可能是镜像，因为一棵树缺失而另一棵树有节点。因此，返回 false。

步骤 2：初始化两个堆栈：为了模拟递归，我们使用两个堆栈。一个堆栈将用于遍历第一棵树，另一个堆栈将用于遍历第二棵树。我们首先将两棵树的根节点分别推入它们的堆栈。

推入根节点：将第一棵树和第二棵树的根节点分别推入 stack1 和 stack2。

步骤 3：使用堆栈处理节点：现在，我们进入一个循环，该循环一直持续到两个堆栈都不为空。在循环的每次迭代中，我们

弹出节点：从 stack1（对于第一棵树）弹出一个节点，并从 stack2（对于第二棵树）弹出一个节点。

比较节点值：如果节点的值不相等，则返回 false，因为树不可能是镜像。

如果节点值匹配，则我们继续通过将它们推入堆栈来比较它们的子节点。

步骤 4：推入子节点以保持镜像对称性：对于每一对节点，我们按照特定顺序将它们的子节点推入堆栈，以确保我们保持镜像对称性。

左子节点和右子节点比较：将第一个节点的左子节点和第二个节点的右子节点分别推入 stack1 和 stack2。

将第一个节点的右子节点和第二个节点的左子节点分别推入 stack1 和 stack2。

此步骤可确保我们始终将一棵树的左子节点与另一棵树的右子节点进行比较，反之亦然，这是镜像对称性的本质。

步骤 5：处理不匹配的子树：在推入子节点时，请检查一个节点是否有左子节点或右子节点，而另一棵树中的相应节点没有子节点的情况。如果发生这种情况，则返回 false，因为它表示树的结构不匹配。

步骤 6：继续直到两个堆栈都为空：循环一直持续到两个堆栈都为空，这意味着我们已成功比较了所有节点。如果在比较过程中未发现任何不匹配，并且在结束时两个堆栈都为空，则返回 true，因为这两棵树是彼此的镜像。

如果在任何时候一个堆栈比另一个堆栈先为空，则表示树的结构不平衡，我们返回 false。

步骤 7：返回最终结果：如果循环完成并且所有节点都与镜像对称性匹配，则返回 true，表示树是彼此的镜像。如果在任何时候任何比较失败，则返回 false。

输出

 
true   

复杂度分析

时间复杂度

此算法的时间复杂度为 O(n)，其中 n 是树中的节点数。在处理过程中，每个节点都会被访问一次，并且每个步骤中的操作（比较和堆栈操作）都是恒定的，从而得到线性时间复杂度。

空间复杂度

此算法的空间复杂度为 O(h)，其中 h 是树的高度。这是由于用于遍历的 堆栈 使用。在倾斜树的最坏情况下，空间复杂度可能达到 O(n)，但对于平衡树，它是 O(log n)。