对称的二叉树(剑指offer 28)

简介: 请实现一个函数,用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样,那么它是对称的。

一、题目描述



       请实现一个函数,用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样,那么它是对称的。

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

fd181adc14154ed982391240e340aa6d.png

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:


33365a66596b40fe804e5e582c5dee32.png


示例 1:

输入:root = [1,2,2,3,4,4,3]

输出:true


示例 2:

输入:root = [1,2,2,null,3,null,3]

输出:false


限制:

0 <= 节点个数 <= 1000

/**
 * 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) {
    }
}


二、思路讲解



判断二叉树是否对称 :


假设树中任意两个对称节点为L、R


1、L.val == R.val


2、L.left.val == R.right.val


3、L.right.val == R.left.val

     

终止条件: L和R的子树都为null,返回true

                     

L和R的子树一个为null,一个不为null,返回false


L和R的节点值不相等,返回false

     

特例,根节点为null,返回true


三、Java代码实现



public class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;
  TreeNode(int x) { val = x; }
}
class Solution {
    public boolean isSymmetric(TreeNode root) {
//        return root == null ? true : recur(root.left, root.right);
      //树本身为空
      if(root == null) {
        return true;
      } else {
        return recur(root.left, root.right);
      }
    }
    boolean recur(TreeNode L, TreeNode R) {
      //L和R同时达到叶子节点
        if(L == null && R == null) {
          return true;
        }
        if(L == null || R == null || L.val != R.val) {
          return false;
        }
        return recur(L.left, R.right) && recur(L.right, R.left);
    }
}


四、时空复杂度分析



时间复杂度:O(n)

     

空间复杂度: O(n)


相关文章
|
6月前
|
Java C++ Python
leetcode-101:对称二叉树
leetcode-101:对称二叉树
45 0
Leetcode101.对称二叉树
Leetcode101.对称二叉树
27 0
|
1月前
【LeetCode 30】101.对称二叉树
【LeetCode 30】101.对称二叉树
11 1
|
6月前
LeetCode——101——对称二叉树
LeetCode——101——对称二叉树
62 12
LeetCode | 101. 对称二叉树
LeetCode | 101. 对称二叉树
|
6月前
leetcode:对称二叉树
leetcode:对称二叉树
剑指offer 27. 对称的二叉树
剑指offer 27. 对称的二叉树
71 0
|
存储 C++ 容器
剑指Offer - 面试题28:对称的二叉树
剑指Offer - 面试题28:对称的二叉树
70 0
|
Java C++ Python
|
算法 Java
算法打卡Day19_leetcode _101. 对称二叉树
算法打卡Day19_leetcode _101. 对称二叉树
算法打卡Day19_leetcode _101. 对称二叉树