# Tree - 100. Same Tree

100. Same Tree

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Example 1:

Input:
1         1
/ \       / \
2   3     2   3

[1,2,3],   [1,2,3]

Output: true

go：

/**

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

//recursive
func isSameTree(p *TreeNode, q *TreeNode) bool {
if p == nil && q == nil {
return true
}
if (p == nil && q != nil) || (p != nil && q == nil) {
return false
}

if p.Val != q.Val {
return false
} else {
return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}
}

/* iteratively
func isSameTree(p *TreeNode, q *TreeNode) bool {
if p == nil && q == nil {
return true
}
if (p == nil && q != nil) || (p != nil && q == nil) {
return false
}

stackp := list.New()
stackq := list.New()
stackp.PushBack(p)
stackq.PushBack(q)
for stackp.Len() != 0 || stackq.Len() != 0 {
ep, eq := stackp.Back(), stackq.Back()
stackp.Remove(ep)
stackq.Remove(eq)
curp, curq := ep.Value.(*TreeNode), eq.Value.(*TreeNode)
if curp.Val != curq.Val {
return false
}

if curp.Left != nil && curq.Left != nil{
stackp.PushBack(curp.Left)
stackq.PushBack(curq.Left)
} else if curp.Left == nil && curq.Left == nil {

} else {
return false
}

if curp.Right != nil && curq.Right != nil{
stackp.PushBack(curp.Right)
stackq.PushBack(curq.Right)
} else if curp.Right == nil && curq.Right == nil {

} else {
return false
}

}

return true
}
*/

Nothing just happens, it's all part of a plan.