一、题目描述

  【JZ58】请实现一个函数，用来判断一棵二叉树是否是对称的。注意，若是一个二叉树同此二叉树的镜像是一样的，定义其为对称的。
  知识点：二叉树，递归
  难度：☆java

二、解题思路

  根据题意中对称二叉树的定义，咱们能够采用递归的思路来解决。

  根据上图可知：若知足对称二叉树，必须知足：
  一、L 和 R 相同；
  二、L->left 和 R->right 相同；
  三、L->right 和 R->left 相同。node

  根据这种规律，咱们能够从根节点开始往下遍历。
  一、先对比 root 和 root，确定相同。
  二、接着对比 root.left 和 root.right，若是不相同，则直接返回 false；若是相同，则继续对比 left.left 和 right.right 是否相同，left.right 和 right.left 是否相同。
  三、当须要对比是否相同的两个节点同时为 null，返回 true；不一样时为 null，则返回 false。web

三、解题代码

package pers.klb.jzoffer.veryhard;

import pers.klb.jzoffer.simple.TreeNode;

/** * @program: JzOffer2021 * @description: 对称的二叉树 * @author: Meumax * @create: 2020-08-12 19:28 **/
public class SymmetricalTree {
    boolean isSymmetrical(TreeNode pRoot) {
        return isSame(pRoot,pRoot);
    }

    private boolean isSame(TreeNode node1, TreeNode node2) {
        if (node1 == null && node2 == null) return true;
        if (node1 == null || node2 == null) return false;
        return node1.val == node2.val
                && isSame(node1.left, node2.right)
                && isSame(node1.right, node2.left);
    }
}

  时间复杂度：O(N)
  空间复杂度：O(N),最坏状况下，二叉树退化为链表svg

四、解题心得

  本题容易一开始觉得考察某种遍历（前序、中序或后序），但其实否则，虽然也是遍历，关键在于左右两边要同步走，而且是镜像对称地往下走，当走到哪一步发现不相等了，直接返回 false。函数