leetcode刷题记录（四十二）——101. 对称二叉树

（一）问题描述

. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/symmetric-tree/description/给你一个二叉树的根节点 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

 进阶：你可以运用递归和迭代两种方法解决这个问题吗？

（二）解决思路

       比较是否对称的思路可以转化成：比较左子树内侧和右子树内侧是否相等、左子树外侧和右子树外侧是否相等，如果相等，说明二叉树对称。注意，这里不是比较左孩子和右孩子是否相等。

 1. 迭代法

       这里迭代法可以用队列或者栈来完成。以队列为例，左子树内侧和右子树内侧是否相等、左子树外侧和右子树外侧节点在队列中的位置应该是相邻的，这样每次弹出两个元素进行比较，如果一直比较到队列为空，都没有出现不相等的情况，那么就可以断定二叉树是对称的。不相等的情况有三种：

• 左节点为空，右节点不为空
• 左节点不为空，右节点为空
• 左节点和右节点都不为空，但是值不相等

        如果左节点和右节点都为空，但是队列还不为空，那说明目前处理的节点是最底层的节点，但比较并没有结束，要将加入到队列里的节点都比较完。

/*** 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) {//这里实现队列要用LinkedList,不要用ArrayDeque//ArrayList不支持添加空元素Queue<TreeNode> qe=new LinkedList<>();if(root==null) return true;//比较的是左右子树，不包括根节点//可以理解为后序遍历的思想，把左右子树先加进来，不用管最顶层的根节点qe.add(root.left);qe.add(root.right);while(!qe.isEmpty()){TreeNode leftNode=qe.poll();TreeNode rightNode=qe.poll();//两个节点都为空的情况if(leftNode==null&&rightNode==null){continue;}//三种不相等情况if(leftNode==null||rightNode==null||leftNode.val!=rightNode.val){return false;}//注意添加的顺序，要比较的两个节点放在一起//判断一下是否为空，避免空指针的问题if(leftNode!=null)qe.add(leftNode.left);if(rightNode!=null)qe.add(rightNode.right);if(leftNode!=null)qe.add(leftNode.right);if(rightNode!=null)qe.add(rightNode.left);}return true;}
}

2. 递归法

 写好递归法需要明确的三个部分：

• 传入参数和返回值，显然这里的参数是左节点和右节点，返回值是判断的结果，true和false；
• 处理逻辑，在这个问题中是左节点和右节点相等时，接下来需要再比较这两个节点下的两个子树的内侧和外侧是否分别相等；
• 终止条件，在这个问题当中即传入的左右节点同时为空、左节点为空但右节点不为空、右节点不为空但左节点为空、左右节点的值不相等四种情况。其中左右节点同时为空，说明遍历已经完成，并且两侧子树层数相同，在此之前都没有出现比较不相等的情况，应当返回true。其他三种情况都是比较出现了不相等，应当返回false。

/*** 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 symmetric(TreeNode left,TreeNode right){//终止条件if(left!=null&&right==null) return false;if(left==null&&right!=null) return false;if(left==null&&right==null) return true;if(left.val!=right.val) return false;//如果相等，再比较它们子树的内外侧boolean outSide=symmetric(left.right,right.left);boolean inSide=symmetric(left.left,right.right);return outSide&&inSide;}public boolean isSymmetric(TreeNode root) {return symmetric(root.left,root.right);}
}