剑指 Offer 28.对称的二叉树

剑指 Offer 28. 对称的二叉树

解题思路：递归

本题和 剑指 Offer 27. 二叉树的镜像 如出一辙。

对于一个二叉树是否对称的定义即是看该二叉树的左子树与右子树是否满足互为镜像的关系。

所以，和二叉树的镜像问题一样，我们依旧可以使用递归的思想解决本题。

递归算法明确的两个目标：

1. 返回条件
2. 递推算法

我们可以自己创建一个方法 isMirror ，输入两个二叉树的根节点，该方法用于判断两个二叉树是否互为镜像

1. 返回条件
   • 如果输入的两个根节点均为空，则返回 true
   • 如果仅有一个根节点为空，另一个根节点不为空，则返回 false
   • 如果输入的两个根节点对应的 val 值不相同，则返回 false
2. 递推算法
   如果不在递归的返回条件内，我们就要使用递推公式将大规模问题转换为小规模的子问题。
   假设两个根节点分别为：A，B
   如果两棵树互为镜像，则满足：
   A 的左子树与 B 的右子树互为镜像；B 的左子树与 A 的右子树互为镜像

代码

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null){
            return true;
        }
        return isMirror(root.left,root.right);
    }
    private boolean isMirror(TreeNode node1,TreeNode node2) {
        if(node1 == null && node2 == null){
            return true;
        }
        if(node1 == null || node2 == null){
            return false;
        }
        if(node1.val != node2.val){
            return false;
        }
        return isMirror(node1.left,node2.right) && isMirror(node1.right,node2.left);
    }
}

复杂度分析

• 时间复杂度：O(N)
  N 为二叉树的节点个数，每次执行 isMirror 方法就可以判断出一对节点，最多调用 N/2 次 isMirror 方法，所以该算法的时间复杂度为：O(N)
• 空间复杂度：
  额外使用的空间为递归栈的深度，最差情况，二叉树退化为链表，系统会使用 O(N) 的额外空间