对称的二叉树

---

题目：

题解

1、辅助队列

• 解题思路：将每一层数据放入集合，因为对称，集合左和集合右正好相反

• 复杂度分析：

  • 时间复杂度 O(N) ： N 为二叉树的节点数量，即 BFS 需循环 N 次，占用 O(N) 。
  • 空间复杂度 O(N)

• 代码：

  class Solution {
      public boolean isSymmetric(TreeNode root) {
          if (root == null) {
              return true;
          }
  
          // 初始化队列
          Queue<TreeNode> queue = new LinkedList() {{
              add(root);
          }};
  
          int count = 0;
          while (!queue.isEmpty()) {
              // 每次循环都创建一个新的集合，每次放树每一层的数。
              List tmp = new ArrayList();
  
              for (int i = queue.size(); i > 0; i--) {
                  TreeNode poll = queue.poll();
  
                  // 如果结点为null，直接给tmp赋-1，退出当前循环
                  if( poll == null) {
                      tmp.add(-1);
                      continue;
                  }
  
                  // 如果结点不为null，则将结点的值给tmp
                  if(poll != null) {
                      tmp.add(poll.val);
                  }
  
                  // 只要结点不为空，就将结点的左右子结点存入队列，如果子孩子结点为null，直接给tmp赋-1，退出当前循环
                  if(poll != null) {
                      queue.add(poll.left);
                      queue.add(poll.right);
                  }
              }
  
              // 将树该层的tmp，因为是对称的，所以分开两部分，然后比较后一部分的反转和前一部分是否相等，相等则继续，直到队列为空，说明全部遍历结束，是对称的，返回true
              int size = tmp.size() / 2;
              if (count == 0) {
                  count++;
                  continue;
              }
  
              if (tmp.size() % 2 == 0 ) {
                  List<Integer> a = tmp.subList(0, size);
                  List<Integer> b = tmp.subList(size , tmp.size());
                  Collections.reverse(b);
                  boolean equals = a.equals(b);
                  if (equals == true) {
                      count++;
                      continue;
                  }
              }return false;
  
          }
          return true;
      }
  }

2、递归法

• 解题思路：

  • 对称二叉树定义： 对于树中 任意两个对称节点 L 和 R ，一定有：
    • L.val = R.val：即此两对称节点值相等。
    • L.left.val = R.right.val ：即 L 的 左子节点 和 R 的 右子节点 对称；
    • L.right.val = R.left.val ：即 L 的 右子节点 和 R 的 左子节点 对称。

• 复杂度分析：

  • 时间复杂度 O(N) ： 其中 NN 为二叉树的节点数量，每次执行 recur() 可以判断一对节点是否对称，因此最多调用 N/2 次 recur() 方法。

  • 空间复杂度 O(N) ： 最差情况下（见下图），二叉树退化为链表，系统使用 O(N) 大小的栈空间。

• 代码：

  class Solution2 {
      public boolean isSymmetric(TreeNode root) {
          // 根节点为空直接返回
          if (root == null) {
              return true;
          }
  
          return recur(root.left,root.right);
  
          // return root == null ? true : recur(root.left, root.right);
      }
  
      // 从顶至底递归，判断每对节点是否对称，从而判断树是否为对称二叉树。
      private boolean recur(TreeNode L, TreeNode R) {
          // 当 L 和 R 同时越过叶节点： 此树从顶至底的节点都对称，因此返回 true;
          if (L == null && R == null) {
              return true;
          }
  
          // 当 L 或 R 中只有一个越过叶节点: 此树不对称;当节点 L 值 != 节点 R 值： 此树不对称;返回false
          if (L == null || R == null || L.val != R.val) {
              return false;
          }
  
          // 左 = 右，右 = 左
          return recur(L.left,R.right) && recur(L.right,R.left);
      }
  }