算法:
本题目主要是对题目的理解,对称二叉树是一个镜像的概念:
举个形象的例子,对称二叉树就是沿着根节点垂直画一条线,然后两边的左右子树对折起来能够重合,这就是对称二叉树,具体场景如下所示:
1.空节点和一个节点是对称的
2.只有左子树或者右子树的节点不是对称节点
3.父节点相同,左子树的左节点==右子树的右节点,
左子树的右节点==右子树的左节点,这个也是对称节点。
(备注:递归实现这些判断就可以。)
题目1:对称二叉树
https://leetcode-cn.com/problems/symmetric-tree/
代码实现:
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isSymmetric(root *TreeNode) bool {
if root == nil {
return true
}
return check(root.Left,root.Right)
}
func check(l, r *TreeNode) bool {
if l == nil && r == nil {
return true
}
if l==nil || r ==nil {
return false
}
return l.Val == r.Val && check(l.Left,r.Right) && check(l.Right,r.Left)
}
// 算法:镜像的概念,L树的左子树与R树的右子树相同,L树的右子树与R树的左子树相同
执行结果:
小结:对称二叉树算是树操作的一种经典题目,对于这种题目的解法,递归是一种很好的方式,算是基本题型之一,是一定要掌握的。