symmetric-tree.go

// https://leetcode.com/problems/symmetric-tree/

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSymmetric(root *TreeNode) bool {
    if root != nil && !isEqual(root.Left, root.Right) {
        return false
    }
    
    if root == nil || root.Left == nil {
        return true
    }
    
    leftCh := walk(root.Left, true)
    rightCh := walk(root.Right, false)
    
    for {
        left, okLeft := <- leftCh
        right, okRight := <- rightCh
        
        if okLeft != okRight {
            return false
        }
        
        if !okLeft {
            return true
        }
        
        if !isEqual(left, right) {
            return false
        }
    }
    
    return true
}

func isEqual(a, b *TreeNode) bool {
    if a == nil && b == nil {
        return true
    }
    
    if (a == nil && b != nil) || (a != nil && b == nil) {
        return false
    }
    
    return a.Val == b.Val
}

func walk(root *TreeNode, left bool) chan *TreeNode {
    ch := make(chan *TreeNode)
    
    go func () {
        queue := []*TreeNode{root}

        for len(queue) > 0 {
            top := queue[0]
            queue = queue[1:]

            ch <- top
            
            if top == nil {
                continue
            }
            
            if left {
                queue = append(queue, top.Left)
                queue = append(queue, top.Right)
            } else {
                queue = append(queue, top.Right)
                queue = append(queue, top.Left)
            }
        }
        
        close(ch)
    }()
    
    return ch
}