Simple Concurrent Recursion In Go (Utilizes Parallel Capabilities)


  • 0
    E

    Here is my solution in Go. It uses a sort of Concurrent "Recursion". In a way, it inverts every node of the binary tree at the same time. Every node is treated with it's own Goroutine. This created a significant speed boost over simply pushing the nodes onto a stack using normal recursion and over doing it iteratively.

    import "sync"
     
    func invertTree(root *TreeNode) *TreeNode {
        var recInv func(r *TreeNode)
        var wg sync.WaitGroup
        
        recInv = func(r *TreeNode) {
            defer wg.Done()
    	if r != nil {
    	    wg.Add(2)
    	    go recInv(r.Left)
                go recInv(r.Right)
    		    
                temp := r.Left
                r.Left = r.Right
    	    r.Right = temp
    	}
       }
       wg.Add(1)
       recInv(root)
    	
       wg.Wait()
       return root
    }
    

Log in to reply
 

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