Day51 对称二叉树

给定一个二叉树，检查它是否是镜像对称的

https://leetcode-cn.com/problems/symmetric-tree/

二叉树 [1,2,2,3,4,4,3] 是对称的。

 1

/
2 2
/ \ /
3 4 4 3

[1,2,2,null,3,null,3] 则不是镜像对称的:

1

/
2 2
\
3 3

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

Java解法

思路：

• 按照二叉树的下标与层数的关系，可以判断出需要对称的数据的样式
• 使用递归处理，校验当前层是否对称，生成下层数据，递归校验，全为空时退出

package sj.shimmer.algorithm.m3_2021;

import java.util.ArrayList;
import java.util.List;

import sj.shimmer.algorithm.TreeNode;

/**
 * Created by SJ on 2021/3/17.
 */

class D51 {
    public static void main(String[] args) {
        System.out.println(isSymmetric(TreeNode.getInstance(new Integer[]{1,2,2,3,4,4,3})));
        System.out.println(isSymmetric(TreeNode.getInstance(new Integer[]{1,2,2,null,3,null,3})));
    }
    public static boolean isSymmetric(TreeNode root) {
        List<TreeNode> treeNodeList = new ArrayList<>();
        if (root != null) {
            treeNodeList.add(root.left);
            treeNodeList.add(root.right);
          return check(treeNodeList);
        }else {
            return true;
        }
    }
    public static boolean check(List<TreeNode> treeNodeList) {
        //转换为List数组
        List<TreeNode> temp = new ArrayList<>();
        int size = treeNodeList.size();
        boolean isEmpty = true;
        for (int i = 0; i < size; i++) {
            //第index层的父层 数量为index个；所以比较 index/2前后是否一致
            if (i>size/2){//已对比完成，直接加入
                if (treeNodeList.get(i)==null) {
                    temp.add(null);
                    temp.add(null);
                }else {
                    isEmpty = false;
                    temp.add(treeNodeList.get(i).left);
                    temp.add(treeNodeList.get(i).right);
                }
                continue;
            }
            if (treeNodeList.get(i) == null) {
                if (treeNodeList.get(size-1-i)==null){
                    temp.add(null);
                    temp.add(null);
                }else{
                    return false;
                }
            } else {
                if (treeNodeList.get(size - 1 - i) == null||treeNodeList.get(i).val != treeNodeList.get(size - 1 - i).val) {
                    return false;
                }
                isEmpty = false;
                temp.add(treeNodeList.get(i).left);
                temp.add(treeNodeList.get(i).right);
            }
        }
        if (isEmpty) {
            return true;
        }
        return check(temp);
    }
}

image

官方解

https://leetcode-cn.com/problems/symmetric-tree/solution/dui-cheng-er-cha-shu-by-leetcode-solution/

1. 递归

   官方解效率很高，原因是将问题转换为 满足什么条件互为镜像，使用双指针遍历处理，指针镜像的遍历

   public boolean isSymmetric(TreeNode root) {
   >     return check(root, root);
   > }
   > 
   > 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);
   > }
   > 
   > ```
   >
   > ![image](https://img.haomeiwen.com/i3026588/ddc2d6a52b61685f.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
   

   • 时间复杂度： O(n)
   • 空间复杂度： O(n)

2. 迭代

   使用队列来对结点入栈，将两棵树，镜像入对，再进行出队判断处理

   class Solution {
       public boolean isSymmetric(TreeNode root) {
           return check(root, root);
       }
   
       public boolean check(TreeNode u, TreeNode v) {
           Queue<TreeNode> q = new LinkedList<TreeNode>();
           q.offer(u);
           q.offer(v);
           while (!q.isEmpty()) {
               u = q.poll();
               v = q.poll();
               if (u == null && v == null) {
                   continue;
               }
               if ((u == null || v == null) || (u.val != v.val)) {
                   return false;
               }
   
               q.offer(u.left);
               q.offer(v.right);
   
               q.offer(u.right);
               q.offer(v.left);
           }
           return true;
       }
   }
   

   • 时间复杂度： O(n)
   • 空间复杂度： O(n)