Posted 2021-04-19Updated 2021-06-08剑指offer2 minutes read (About 245 words)0 visits

剑指 Offer 28. 对称的二叉树【递归】

题目描述

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

例如，二叉树 [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

示例 1：

1 2	输入：root = [1,2,2,3,4,4,3] 输出：true

示例 2：

1 2	输入：root = [1,2,2,null,3,null,3] 输出：false

解题思路

方法：递归

递归判断对称结点是否值相等

代码实现

class Solution28 {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return Symmetric(root.left, root.right);
    }

    public boolean Symmetric(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        }
        if (left == null || right == null) {
            return false;
        }
        if (left.val != right.val) {
            return true;
        }
        return Symmetric(left.right, right.left) && Symmetric(left.left, right.right);

    }
}