剑指 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：
输入：root = [1,2,2,3,4,4,3]
输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3]
输出：false

限制：
0 <= 节点个数 <= 1000
链接：https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/
注意：本题与主站 101 题相同：https://leetcode-cn.com/problems/symmetric-tree/

解题思路

做递归思考：
递归的函数要干什么？
函数的作用是判断传入的两个树是否镜像。
输入：TreeNode left, TreeNode right
输出：是：true，不是：false
递归停止的条件是什么？
左节点和右节点都为空 -> 倒底了都长得一样 ->true
左节点为空的时候右节点不为空，或反之 -> 长得不一样-> false
左右节点值不相等 -> 长得不一样 -> false
从某层到下一层的关系是什么？
要想两棵树镜像，那么一棵树左边的左边要和二棵树右边的右边镜像，一棵树左边的右边要和二棵树右边的左边镜像
调用递归函数传入左左和右右
调用递归函数传入左右和右左
只有左左和右右镜像且左右和右左镜像的时候，我们才能说这两棵树是镜像的
怎么调用递归函数？
调用递归函数，我们想知道它的左右孩子是否镜像，传入的值是root的左孩子和右孩子。这之前记得判root是不是null。

此外，关于判断“是不是”的递归题目，可以用return+与操作的方法，如

return Traverse(node_1.Left, node_2.Right) && Traverse(node_1.Right, node_2.Left)

解题代码

golang

// 分别遍历
func Traverse(node_1, node_2 *TreeNode) bool {
    if node_1 == nil && node_2 == nil {
        return true
    }
    if (node_1 == nil && node_2 != nil) || (node_1 != nil && node_2 == nil) {
        return false
    }
    if node_1.Val != node_2.Val {
        return false
    }
    return Traverse(node_1.Left, node_2.Right) && Traverse(node_1.Right, node_2.Left)
}

// 判断是不是平衡二叉树
func isSymmetric(root *TreeNode) bool {
    if root == nil {
        return true
    }
    result := Traverse(root.Left, root.Right)
    return result
}

python

class Solution:
    def traverse(self, l: TreeNode, r: TreeNode) -> bool:
        # 判断：左右皆空 左右一个为空一个为不空 左右都不空
        if not l and not r:
            return True
        if (not l and r) or (l and not r):
            return False
        if l.val != r.val:
            return False
        return self.traverse(l.left, r.right) & self.traverse(l.right, r.left)

    def isSymmetric(self, root: TreeNode) -> bool:
        if not root:
            return True
        return self.traverse(root.left, root.right)

执行结果

执行结果：通过
执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：2.9 MB, 在所有 Go 提交中击败了89.50%的用户