isSameTree

isSameTree.go

/**
https://leetcode.com/problems/same-tree/submissions/
BFS 
Runtime: 0 ms, faster than 100.00% of Go online submissions for Same Tree.
Memory Usage: 2.2 MB, less than 50.00% of Go online submissions for Same Tree
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func isSameTree(p *TreeNode, q *TreeNode) bool {
    
    // I'm going to use modified BFS for both trees
    q1 := make([]*TreeNode,0)
    q2 := make([]*TreeNode,0)
    
    var x,y *TreeNode
    
    q1 = append(q1, p)
    q2 = append(q2, q)
    for len(q1) != 0 || len(q2) != 0 {
        if len(q1) != len(q2){
            return false            
        }
        // extract elements
        x, q1 = q1[0], q1[1:]
        y, q2 = q2[0], q2[1:]
        if x != nil && y == nil {
            return false
        }
        if x == nil && y != nil {
            return false
        }
        if x != nil && y != nil && x.Val != y.Val{
            return false
        }
        if x != nil  {
            q1 = append(q1, x.Left, x.Right)
        }
        if y != nil {
            q2 = append(q2, y.Left, y.Right)
        }
    }
    return true
}

isSameTreeDFS.go

/**
DFS
Runtime: 0 ms, faster than 100.00% of Go online submissions for Same Tree.
Memory Usage: 2.1 MB, less than 50.00% of Go online submissions for Same Tree.
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func isSameTree(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
    }
    if !((p.Left == nil && q.Left == nil) || (p.Left != nil && q.Left != nil)){
        return false
    }
    if !((p.Right == nil && q.Right == nil) || (p.Right != nil && q.Right != nil)){
        return false
    }
    return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right) 
}