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
}
*/