0101. Symmetric Tree

# 101. Symmetric Tree#

## 题目 #

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

``````
1
/ \
2   2
/ \ / \
3  4 4  3

``````

But the following [1,2,2,null,3,null,3] is not:

``````
1
/ \
2   2
\   \
3    3

``````

Note:

Bonus points if you could solve it both recursively and iteratively.

## 解题思路 #

• 这道题是几道题的综合题。将根节点的左字数反转二叉树，然后再和根节点的右节点进行比较，是否完全相等。
• 反转二叉树是第 226 题。判断 2 颗树是否完全相等是第 100 题。

## 代码 #

``````
package leetcode

import (
"github.com/halfrost/leetcode-go/structures"
)

// TreeNode define
type TreeNode = structures.TreeNode

/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/

// 解法一 dfs
func isSymmetric(root *TreeNode) bool {
if root == nil {
return true
}
return isMirror(root.Left, root.Right)
}

func isMirror(left *TreeNode, right *TreeNode) bool {
if left == nil && right == nil {
return true
}
if left == nil || right == nil {
return false
}
return (left.Val == right.Val) && isMirror(left.Left, right.Right) && isMirror(left.Right, right.Left)
}

// 解法二
func isSymmetric1(root *TreeNode) bool {
if root == nil {
return true
}
return isSameTree(invertTree(root.Left), root.Right)
}

func isSameTree(p *TreeNode, q *TreeNode) bool {
if p == nil && q == nil {
return true
} else if p != nil && q != nil {
if p.Val != q.Val {
return false
}
return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
} else {
return false
}
}

func invertTree(root *TreeNode) *TreeNode {
if root == nil {
return nil
}
invertTree(root.Left)
invertTree(root.Right)
root.Left, root.Right = root.Right, root.Left
return root
}

``````

Apr 8, 2023
Edit this page