📑 题目：101. 对称二叉树

🚀 本题 LeetCode 传送门

题目大意

这一题要求判断 2 颗树是否是左右对称的。

解题思路

• 这道题是几道题的综合题。将根节点的左字数反转二叉树，然后再和根节点的右节点进行比较，是否完全相等。
• 反转二叉树是第 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
}