LeetCode 101. 对称二叉树

要判断一个二叉树是否对称，可以通过递归的方式比较其左右子树是否互为镜像。以下是详细的解答：

解题思路

递归比较：对称二叉树的定义是左子树和右子树互为镜像。因此，可以通过递归比较左子树的左节点与右子树的右节点，以及左子树的右节点与右子树的左节点是否相等来实现。
终止条件：
如果两个节点都为空，说明对称，返回 true。
如果其中一个节点为空而另一个不为空，说明不对称，返回 false。
如果两个节点的值不相等，返回 false。
递归逻辑：如果当前两个节点的值相等，则递归比较它们的左右子节点是否对称。

代码实现class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; }}public class Solution { public boolean isSymmetric(TreeNode root) { if (root == null) { return true; } return compare(root.left, root.right); } private boolean compare(TreeNode left, TreeNode right) { if (left == null && right == null) { return true; } if (left == null || right == null) { return false; } if (left.val != right.val) { return false; } return compare(left.left, right.right) && compare(left.right, right.left); }}代码解释

isSymmetric 方法：
首先检查根节点是否为空，如果为空则直接返回 true（空树被认为是对称的）。
否则，调用 compare 方法比较左子树和右子树。
compare 方法：
终止条件：
如果左右节点都为空，返回 true。
如果其中一个为空而另一个不为空，返回 false。
如果左右节点的值不相等，返回 false。
递归逻辑：如果当前节点的值相等，则递归比较左子树的左节点与右子树的右节点，以及左子树的右节点与右子树的左节点。只有两者都对称时，才返回 true。

示例分析

以输入 root = [1,2,2,3,4,4,3] 为例：

初始调用：比较 root.left（值为 2）和 root.right（值为 2）。
第一层递归：
比较 left.left（值为 3）和 right.right（值为 3）。
比较 left.right（值为 4）和 right.left（值为 4）。
第二层递归：
对于 left.left 和 right.right，它们的子节点均为空，返回 true。
对于 left.right 和 right.left，它们的子节点也均为空，返回 true。
结果：所有递归调用均返回 true，因此最终结果为 true。

复杂度分析

时间复杂度：O(n)，其中 n 是树中节点的数量。每个节点都会被访问一次。
空间复杂度：O(h)，其中 h 是树的高度。递归调用的栈空间取决于树的高度，最坏情况下（树完全不平衡）为 O(n)，最好情况下（树完全平衡）为 O(log n)。

通过递归的方式，可以高效地判断二叉树是否对称。

您可能感兴趣问答

Collapsible

热门标签

热点问答