对称二叉树
题目链接：https://leetcode.cn/problems/symmetric-tree/description/?envType=study-plan-v2&envId=top-100-liked
我的解答：
//方法一：递归 //时间复杂度：O(n) //空间复杂度：O(n) public boolean isSymmetric(TreeNode root) { return isEqual(root.left,root.right); } public boolean isEqual(TreeNode left, TreeNode right){ if(left==null&&right==null){ return true; } if(left==null||right==null){ return false; } if(!isEqual(left.left,right.right) || !isEqual(left.right,right.left)){ return false; } return left.val==right.val; } //方法二：迭代（采用双端队列） //时间复杂度：O(n) //空间复杂度：O(n) public boolean isSymmetric(TreeNode root) { if(root.left==null&&root.right==null){ return true; } if(root.left==null||root.right==null){ return false; } Deque<TreeNode> queue = new LinkedList<>(); queue.addFirst(root.left); queue.addLast(root.right); while(!queue.isEmpty()){ TreeNode left = queue.getFirst(); queue.removeFirst(); TreeNode right = queue.getLast(); queue.removeLast(); if(left.val!=right.val){ return false; } if(left.left!=null&&right.right!=null){ queue.addFirst(left.left); queue.addLast(right.right); } if((left.left==null&&right.right!=null) || (left.left!=null&&right.right==null)){ return false; } if(left.right!=null&&right.left!=null){ queue.addFirst(left.right); queue.addLast(right.left); } if((left.right==null&&right.left!=null) || (left.right!=null&&right.left==null)){ return false; } } return true; }分析：
方法一解题思路：采用递归。递归判断两个对称位置上的节点的值和子树是否也呈对称关系。
方法二解题思路：采用迭代。通过将位置上对称的两个节点分别从队列的头和尾加入队列，每次分别从队列头和尾取出一个节点并删除，判断这两个节点的是否相等，若不相等，则二叉树不对称；若相等，且两个节点位置上对称的子节点都不为空，则按照位置对称关系分别从队列头、尾加入队列，若两个节点位置上对称的子节点存在一方为空但另一方不为空的情况就返回false，不断重复以上过程，若直到队列为空都还未出现不对称的情况，则返回true。
看了官方题解后的解答：
//官方题解的方法一与我的解答的方法一思路一致 //方法一：递归 //时间复杂度：O(n) //空间复杂度：O(n) public boolean isSymmetric(TreeNode root) { return check(root.left, root.right); } public boolean check(TreeNode p, TreeNode q) { if (p == null && q == null) { return true; } if (p == null || q == null) { return false; } return p.val == q.val && check(p.left, q.right) && check(p.right, q.left); } //方法二：迭代（采用队列） //时间复杂度：O(n) //空间复杂度：O(n) public boolean isSymmetric(TreeNode root) { //将root加入队列两次，可以避免单独讨论边界情况（二叉树根节点） return check(root,root); } public boolean check(TreeNode u, TreeNode v){ //队列中连续的两个节点位置上是对称的 Queue<TreeNode> queue = new LinkedList<>(); queue.offer(u); queue.offer(v); while(!queue.isEmpty()){ u = queue.poll(); v = queue.poll(); if(u==null&&v==null){ continue; } if((u==null || v==null) || u.val!=v.val){ return false; } queue.offer(u.left); queue.offer(v.right); queue.offer(u.right); queue.offer(v.left); } return true; }分析：方法二采用队列。首先将二叉树的根节点加入队列两次，这样可以避免单独讨论边界情况。用两个指针u、v同时移动，当u向左孩子移动时v向右孩子移动，当u向右孩子移动时v向左孩子移动，这样队列中连续的两个节点在位置上总是对称的。另外，LinkedList实现的队列是允许插入null的，所以在将对称位置的一对节点加入队列时可以避免单独讨论节点为null的情况。
总结
- 本题可采用递归和迭代两种方法进行解答。
- 引入队列是把递归程序改写成迭代程序的常用方法。
