剑指offer-58、对称二叉树
题⽬描述请实现⼀个函数，⽤来判断⼀棵⼆叉树是不是对称的。注意，如果⼀个⼆叉树同此⼆叉树的镜像是同样
的，定义其为对称的。
例如：下⾯这棵⼆叉树是对称的
下⾯这个就不是对称的：
示例1
输⼊：{8,6,6,5,7,7,5}
返回值：true
示例2：
输⼊：{8,6,9,5,7,7,5}
返回值：false
思路及解答
递归
递归，先判断根节点是否为空，不为空则判断左右⼦树是不是对称。
如果左右⼦树都为空，则返回 true ，如果有⼀个为空，则返回 false ，如果两个都不为空的时候，除了对⽐左右两个节点的值，还需要递归，对⽐左⼦树的左⼦树和右⼦树的右⼦树是否相等，左⼦树的右⼦树和右⼦树的左⼦树是否相等。
public class Solution {
public boolean jude(TreeNode left, TreeNode right) {
// 如果左右两个都为空，则对称
if (left == null && right == null) {
return true;
} else if (left == null || right == null) {
// 如果左右两个有⼀个为空，那么就不对称
return false;
}
// 都不为空的情况，需要判断两个的值，是不是相等
if (left.val != right.val) {
return false;
} else {
// 递归判断，左⼦树的左⼦树和右⼦树的右⼦树，左⼦树的右⼦树和右⼦树的左⼦树
return jude(left.left, right.right) && jude(left.right, right.left);
}
}
public boolean isSymmetrical(TreeNode pRoot) {
// 判断根节点是否为空，如果不为空则判断左右⼦树
return pRoot==null || jude(pRoot.left, pRoot.right);
}
}
[*]时间复杂度：O(n)
[*]空间复杂度：O(n),最坏情况下，⼆叉树退化为链表
迭代
是借助两个队列，按照层次，⼀个是按照从左到右添加元素，另外⼀个队列
是按照从右到左添加元素，挨个取出来，进⾏对⽐，不等则说明不对称，如果相等，则再把其左右⼦树
分别按照不同的顺序添加到队列中。代码如下
public class Solution {
/**
* 迭代法
* 使用双端队列，相当于两个栈
*/
public boolean isSymmetric2(TreeNode root) {
Deque<TreeNode> deque = new LinkedList<>();
deque.offerFirst(root.left);
deque.offerLast(root.right);
while (!deque.isEmpty()) {
TreeNode leftNode = deque.pollFirst();
TreeNode rightNode = deque.pollLast();
if (leftNode == null && rightNode == null) {
continue;
}
if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) {
return false;
}
deque.offerFirst(leftNode.left);
deque.offerFirst(leftNode.right);
deque.offerLast(rightNode.right);
deque.offerLast(rightNode.left);
}
return true;
}
/**
* 迭代法
* 使用普通队列
*/
public boolean isSymmetric3(TreeNode root) {
Queue<TreeNode> deque = new LinkedList<>();
deque.offer(root.left);
deque.offer(root.right);
while (!deque.isEmpty()) {
TreeNode leftNode = deque.poll();
TreeNode rightNode = deque.poll();
if (leftNode == null && rightNode == null) {
continue;
}
if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) {
return false;
}
// 这里顺序与使用Deque不同
deque.offer(leftNode.left);
deque.offer(rightNode.right);
deque.offer(leftNode.right);
deque.offer(rightNode.left);
}
return true;
}
}
[*]空间复杂度为 O(n)
[*]时间复杂度为 O(n) ,每个节点只会⼊队出队⼀次。
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ 谢谢楼主提供！ 感谢分享，下载保存了，貌似很强大 谢谢分享，辛苦了 收藏一下 不知道什么时候能用到 不错，里面软件多更新就更好了 感谢发布原创作品，程序园因你更精彩 感谢分享，学习下。 感谢，下载保存了 过来提前占个楼 东西不错很实用谢谢分享 谢谢分享，试用一下 感谢分享，学习下。 喜欢鼓捣这些软件，现在用得少，谢谢分享！ 不错，里面软件多更新就更好了 感谢分享，学习下。 鼓励转贴优秀软件安全工具和文档！ 感谢分享，学习下。 东西不错很实用谢谢分享 感谢分享，下载保存了，貌似很强大
页:
[1]
2