Golang recursive and iterative solution


  • 0

    Recursive

    func isSymmetric(root *TreeNode) bool {
        if root == nil {
            return true
        }
        return isSame(root.Left, root.Right)
    }
    
    func isSame(parent1, parent2 *TreeNode) bool {
        switch {
        case parent1 == nil && parent2 == nil:
            return true
        case parent1 == nil && parent2 != nil, parent1 != nil && parent2 == nil, parent1.Val != parent2.Val:
            return false
        default:
            return isSame(parent1.Left, parent2.Right) && isSame(parent1.Right, parent2.Left)
        }
    }
    

    Iterative
    (BFS and store a list of values including NULL by level, then check if the table is symmetric)

    func isSymmetric(root *TreeNode) bool {
        if root == nil {
            return true
        }
        
        queue := []*TreeNode{root}
        for len(queue) > 0 {
            qlen := len(queue)
            
            table := []*int{}
            for i := 0; i < qlen; i++ {
                node := queue[0]
                queue = queue[1:]
            
                if node.Left != nil {
                    queue = append(queue, node.Left)
                    table = append(table, &node.Left.Val)
                } else {
                    table = append(table, nil)
                }
                if node.Right != nil {
                    queue = append(queue, node.Right)
                    table = append(table, &node.Right.Val)
                } else {
                    table = append(table, nil)
                }
            }
            
            if !levelSymmetric(table) {
                return false
            }
        }
        return true
    }
    
    func levelSymmetric(t []*int) bool {
        tlen := len(t)
        left, right := 0, tlen - 1
        for left < right {
            if t[left] == nil && t[right] == nil {
                left, right = left + 1, right - 1
                continue
            } else if (t[left] != nil && t[right] == nil) || (t[left] == nil && t[right] != nil) {
                return false
            }
    
            if *t[left] != *t[right] {
                return false
            }
            left, right = left + 1, right - 1
        }
        return true
    }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.