一.题目:对称二叉树
题解与分析
用队列做(广度遍历)
注意这个顺序
(我的想法是利用层序遍历,然后将每一层的数组进行遍历,利用双指针对向走,看时候相等,至于空节点也添加进去,但总在135条测试用例过不去)
func isSymmetric(root *TreeNode) bool {
lis := list.New()
lis.PushBack(root)
lis.PushBack(root)
for lis.Len()!=0{
node1 := lis.Remove(lis.Front()).(*TreeNode)
node2 := lis.Remove(lis.Front()).(*TreeNode)
if node1==nil&&node2==nil{
continue
}
// 一边为空, 一边不为空
if node1==nil||node2==nil{
return false
}
if node1.Val!=node2.Val{
return false
}
// 添加元素,顺序有讲究
lis.PushBack(node1.Left)
lis.PushBack(node2.Right)
lis.PushBack(node1.Right)
lis.PushBack(node2.Left)
}
return true
}
递归
func isSymmetric(root *TreeNode) bool {
return dfs(root.Left, root.Right)
}
func dfs(left *TreeNode, right *TreeNode)bool{
// 注意这里,return true 。如果层序遍历就continue
if left==nil&&right==nil{
return true
}
if left==nil||right==nil{
return false
}
if left.Val!=right.Val{
return false
}
// 注意这里是布尔值,也是一次比较一层(可能不是一层,)
return dfs(left.Left, right.Right)&&dfs(right.Left, left.Right)
}
二.题目:相同二叉树
题解与分析
这道题和101差不多,只不过是顺序变了一下
递归法
func isSameTree(p *TreeNode, q *TreeNode) bool {
return dfs(p, q)
}
func dfs(left *TreeNode, right *TreeNode)bool{
if left==nil&&right==nil{
return true
}
if left==nil||right==nil{
return false
}
if left.Val!=right.Val{
return false
}
return dfs(left.Left, right.Left)&&dfs(left.Right, right.Right)
}
func isSameTree(p *TreeNode, q *TreeNode) bool{
return Compare(p, q)
}
func Compare(p *TreeNode, q *TreeNode)bool{
if p==nil&&q==nil{
return true
}
if p==nil||q==nil{
return false
}
if p.Val!=q.Val{
return false
}
leftstatus := Compare(p.Left, q.Left)
rightstatus := Compare(p.Right, q.Right)
return leftstatus&&rightstatus
}
迭代法
func isSameTree(p *TreeNode, q *TreeNode) bool{
lis := list.New()
lis.PushBack(p)
lis.PushBack(q)
for lis.Len()>0{
node1 := lis.Remove(lis.Front()).(*TreeNode)
node2 := lis.Remove(lis.Front()).(*TreeNode)
if node1==nil&&node2==nil{
continue
}
if node1==nil||node2==nil{
return false
}
if node1.Val!=node2.Val{
return false
}
lis.PushBack(node1.Left)
lis.PushBack(node2.Left)
lis.PushBack(node1.Right)
lis.PushBack(node2.Right)
}
return true
}
三.题目
题解与分析
这是一篇很详细的讲解递归的题解,点击查看
题解参考:此处链接的大佬的题解
有的题解说可以用kmp算法做。
递归
func isSubtree(root *TreeNode, subRoot *TreeNode) bool {
// 递归
if root==nil&&subRoot==nil{
return true
}
if root==nil||subRoot==nil{
return false
}
// 这里的三种情况是 || 的关系。满足一种(两树相等,左节点和subRoot等, 右节点和subRoot等)
return isSubtree(root.Right, subRoot)||isSubtree(root.Left, subRoot)||isSame(root, subRoot)
}
func isSame(s *TreeNode, t *TreeNode)bool{
if s==nil&&t==nil{
return true
}
if s==nil||t==nil{
return false
}
if s.Val!=t.Val{
return false
}
// 这里是&& 的关系,必须严格相等,还有要注意的是顺序
return isSame(s.Left, t.Left)&&isSame(s.Right, t.Right)
}