一.题目：对称二叉树

leetcode:101

题解与分析

用队列做（广度遍历）

注意这个顺序
(我的想法是利用层序遍历，然后将每一层的数组进行遍历，利用双指针对向走，看时候相等，至于空节点也添加进去,但总在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)
}

二.题目：相同二叉树

leetcode:100

题解与分析

这道题和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)
}