今天是 8 月日更的第三天，今天带来的题目是对称二叉树的解法，正文如下 。
题目：
给定一个二叉树，检查它是否是镜像对称的。
Example:
思路分析:
如果一个树的左子树与右子树镜像对称，那么这个树是对称的。
那么俩个树在什么情况下互为镜像呢！
我们可以定义满足以下俩种条件的树，互为镜像：
它们的根节点具有相同的值
每个树的右子树都与另一个树的左子树镜像对称
首先，我们想到的就是用递归的方式来解决。
我们将根节点的左子树记做 left，右子树记做 right。通过同步移动两个指针的方法来遍历这棵树，比较 left 是否等于 right，不等的话直接返回就可以了。如果相当，比较 left 的左节点和 right 的右节点，再比较 left 的右节点和 right 的左节点。
递归实现：
/** * Definition for a binary tree node. * public 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; * } * } */class Solution { public boolean isSymmetric(TreeNode root) { //调用递归函数，比较左节点，右节点 return isSame(root, root); }
public boolean isSame(TreeNode p, TreeNode q) { //递归的终止条件是两个节点都为空 if (p == null && q == null) { return true; } //或者两个节点中有一个为空 if (p == null || q == null) { return false; } //两个节点的值相等 //再递归的比较 左节点的左孩子 和 右节点的右孩子 //以及比较 左节点的右孩子 和 右节点的左孩子 return p.val == q.val && isSame(p.left, q.right) && isSame(p.right, q.left); }}
复制代码
除了使用递归的方式，我们还可以采用迭代的方式来实现对称二叉树。
回想下递归的实现：
当两个子树的根节点相等时，就比较左子树的 left 和 右子树的 right，这个比较是用递归实现的。
现在我们改用队列来实现，思路如下：
首先从队列中拿出两个节点(left 和 right)比较
将 left 的 left 节点和 right 的 right 节点放入队列
将 left 的 right 节点和 right 的 left 节点放入队列
迭代实现
class Solution { public boolean isSymmetric(TreeNode root) { if(root==null || (root.left==null && root.right==null)) { return true; } //用队列保存节点 LinkedList<TreeNode> queue = new LinkedList<TreeNode>(); //将根节点的左右孩子放到队列中 queue.add(root.left); queue.add(root.right); while(queue.size()>0) { //从队列中取出两个节点，再比较这两个节点 TreeNode left = queue.removeFirst(); TreeNode right = queue.removeFirst(); //如果两个节点都为空就继续循环，两者有一个为空就返回false if(left==null && right==null) { continue; } if(left==null || right==null) { return false; } if(left.val!=right.val) { return false; } //将左节点的左孩子， 右节点的右孩子放入队列 queue.add(left.left); queue.add(right.right); //将左节点的右孩子，右节点的左孩子放入队列 queue.add(left.right); queue.add(right.left); } return true; }}
复制代码
最后
复杂度分析
递归解法：假设树上一共 n 个节点。
时间复杂度：这里遍历了这棵树，渐进时间复杂度为 O(n)。空间复杂度：这里的空间复杂度和递归使用的栈空间有关，这里递归层数不超过 nn，故渐进空间复杂度为 O(n)。
迭代解法：
时间复杂度：O(n)。空间复杂度：这里需要用一个队列来维护节点，每个节点最多进队一次，出队一次，队列中最多不会超过 n 个点，故渐进空间复杂度为 O(n)。
评论