LeetCode101——对称二叉树
原题链接：https://leetcode-cn.com/problems/symmetric-tree/description/
题目描述：
知识点：递归，队列
思路分析：
（1）思路一：
翻转根结点的右子树，比较与根结点的左子树是否相同。
（2）思路二：
层序遍历二叉树，判断每一层中的元素是否符合回文的性质。
（3）思路三：
递归地判断根结点的左子树和右子树是否是对称的。
思路的具体实现：
（1）思路一：
a.如果root结点为null，则直接返回true。
b.如果root结点没有任何孩子，返回true。
c.如果root结点只有左孩子或者只有右孩子，返回false。
d.判断root结点的左子树和右子树翻转之后的树是否相同，如果相同，则返回true；不相同，则返回false。
（2）思路二：
a.如果root结点为null，则直接返回true。
b.新建一个队列，并将根结点入队。
c.在while循环中，层序遍历该根结点对应的二叉树。
c-1：记录队列中的元素个数level。
c-2：新建一个List类型的变量list，用来记录每一层的结点。
c-3：while(level > 0)进行如下循环：
c-3-1：让level值-1。
c-3-2：让队首元素temp出队并将其加入到list中。
c-3-3：如果temp不为null，则将其左右孩子入队。（这里不用判断左右孩子是否为空，而改为判断temp是否为空。因为在本题中，为了比较每一层左右两边的对称性，空也是需要入队并最终出队加入list的。）
d.设立一个指针从list首开始往后走，另一个指针从list尾开始往前走，比较两个指针所指位置的值是否相等，如果不相等，直接返回false。
e.结束整个层序遍历后，直接返回true。
（3）思路三：
a.如果root结点为null，则直接返回true。
b.设立一个函数isSymmetric(TreeNode node1, TreeNode node2)，传入两个参数root.left和root.right。
c.递归地实现b中新建的函数。
c-1：如果node1和node2均为空，返回true。
c-2：如果node1或者node2中只有一个为空，返回false。
c-3：如果node1的val值和node2的val值不相等，返回false。
c-4：递归地调用isSymmetric(TreeNode node1, TreeNode node2)，判断node1的左子树和node2的右子树是否对称，以及node1的右子树和node2的左子树是否对称，即返回isSymmetric(node1.left, node2.right) && isSymmetric(node1.right, node2.left)。
JAVA代码：
（1）思路一：
public boolean isSymmetric(TreeNode root) {
if(root == null) {
return true;
}else if(root.left == null && root.right == null) {
return true;
}else if(root.left != null && root.right == null) {
return false;
}else if(root.left == null && root.right != null) {
return false;
}else {
return isSameTree(root.left, inverseTree(root.right));
}
}
private TreeNode inverseTree(TreeNode root) {
if(root == null) {
return null;
}
inverseTree(root.left);
inverseTree(root.right);
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
return root;
}
private boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q == null) {
return true;
}else if(p == null && q != null) {
return false;
}else if(p != null && q == null) {
return false;
}else if(p.val != q.val) {
return false;
}
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}（2）思路二：
public boolean isSymmetric(TreeNode root) {
if(root == null) {
return true;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()) {
int level = queue.size();
List<TreeNode> list = new ArrayList<>();
while(level > 0) {
level--;
TreeNode temp = queue.poll();
list.add(temp);
if(temp != null) {
queue.add(temp.left);
queue.add(temp.right);
}
}
int i = 0;
int j = list.size() - 1;
while(i < j) {
if(list.get(i) == null && list.get(j) == null) {
i++;
j--;
continue;
}
if(list.get(i) == null && list.get(j) != null) {
return false;
}
if(list.get(i) != null && list.get(j) == null) {
return false;
}
if(list.get(i).val != list.get(j).val) {
return false;
}
i++;
j--;
}
}
return true;
}（3）思路三：
public boolean isSymmetric(TreeNode root) {
if(root == null) {
return true;
}
return isSymmetric(root.left, root.right);
}
private boolean isSymmetric(TreeNode node1, TreeNode node2) {
if(node1 == null && node2 == null) {
return true;
}else if(node1 == null && node2 != null){
return false;
}else if(node1 != null && node2 == null){
return false;
}else if(node1.val != node2.val){
return false;
}
return isSymmetric(node1.left, node2.right) && isSymmetric(node1.right, node2.left);
}复杂度分析：
（1）思路一：
a.时间复杂度：O(n)，n为树的结点数
b.空间复杂度：O(n)
（2）思路二：
a.时间复杂度：O(n)
b.空间复杂度：O(n)
（3）思路三：
a.时间复杂度：O(n)
b.空间复杂度：O(n)