对称二叉树
难度:
标签:
题目描述
给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例 1：
输入：root = [1,2,2,3,4,4,3] 输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3] 输出：false
提示：
- 树中节点数目在范围
[1, 1000]内 -100 <= Node.val <= 100
进阶：你可以运用递归和迭代两种方法解决这个问题吗？
代码结果
运行时间: 44 ms, 内存: 15.1 MB
/*
* 思路：
* 与常规递归方法类似，但使用Java Stream来实现。
* 利用Java Stream来简化数据操作和代码的可读性。
*/
import java.util.stream.Stream;
public class Solution {
public boolean isSymmetric(TreeNode root) {
// 空树是对称的
if (root == null) return true;
// 从根节点的左右子树开始判断
return isMirror(root.left, root.right);
}
private boolean isMirror(TreeNode t1, TreeNode t2) {
// 利用Stream来判断两节点是否相等并进行递归
return Stream.of(t1, t2)
.allMatch(n -> n == null) ||
(t1 != null && t2 != null && t1.val == t2.val &&
isMirror(t1.left, t2.right) &&
isMirror(t1.right, t2.left));
}
}
解释
方法:
这个题解使用递归的方式来判断二叉树是否对称。主要思路是同时从左右子树开始递归遍历，比较对应位置节点的值是否相等。如果左右子树都为空，说明对称；如果只有一个子树为空，说明不对称；如果两个子树的节点值不相等，也说明不对称。在递归过程中，要将左子树的左孩子和右子树的右孩子进行比较，左子树的右孩子和右子树的左孩子进行比较。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在递归函数中，当左右子树都为空时直接返回True，这种处理方式是否能正确处理所有对称树的情况，包括只有一个根节点的树？
▷🦆
递归解法中，如果左右子树的结构相同但是节点值不同，如何确保递归仍然能准确判断出不对称？
▷🦆
您提到可以使用迭代和递归两种方法解决问题，请问迭代方法具体是如何实现的？
▷🦆
在递归函数中，存在多处对节点为空的检查，是否可以通过优化减少这些检查以提高代码效率？
▷