剑指offer-58、对称二叉树

题⽬描述请实现⼀个函数⽤来判断⼀棵⼆叉树是不是对称的。注意如果⼀个⼆叉树同此⼆叉树的镜像是同样的定义其为对称的。例如下⾯这棵⼆叉树是对称的下⾯这个就不是对称的示例1输⼊{8,6,6,5,7,7,5}返回值true示例2输⼊{8,6,9,5,7,7,5}返回值false思路及解答递归递归先判断根节点是否为空不为空则判断左右⼦树是不是对称。如果左右⼦树都为空则返回 true 如果有⼀个为空则返回 false 如果两个都不为空的时候除了对⽐左右两个节点的值还需要递归对⽐左⼦树的左⼦树和右⼦树的右⼦树是否相等左⼦树的右⼦树和右⼦树的左⼦树是否相等。javapublic 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 pRootnull || jude(pRoot.left, pRoot.right); } }时间复杂度O(n)空间复杂度O(n),最坏情况下⼆叉树退化为链表迭代是借助两个队列按照层次⼀个是按照从左到右添加元素另外⼀个队列是按照从右到左添加元素挨个取出来进⾏对⽐不等则说明不对称如果相等则再把其左右⼦树分别按照不同的顺序添加到队列中。代码如下javapublic class Solution { /** * 迭代法 * 使用双端队列相当于两个栈 */ public boolean isSymmetric2(TreeNode root) { DequeTreeNode 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) { QueueTreeNode 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; } }