Golang iterative, with fast-path (no queue ops) for linked-list case


  • 0
    A
    func maxDepth(root *TreeNode) int {
    	type qNode struct {
    		n *TreeNode
    		d int
    	}
    
    	if root == nil {
    		return 0
    	}
    
    	maxDepth := 1
    	q := []qNode{qNode{n: root, d: 1}}
    all:
    	for {
    		cur := q[0] // PeekFront
    
    	fast:
    		for {
    			if cur.d > maxDepth {
    				maxDepth = cur.d
    			}
    			if cur.n.Left != nil && cur.n.Right != nil {
    				q = append(q, qNode{cur.n.Left, cur.d + 1}) // Only enqueue if we have both left and right children
    				cur.n = cur.n.Right                         // But don't enqueue both children, just keep running
    			} else if cur.n.Left != nil { // One child case
    				cur.n = cur.n.Left
    			} else if cur.n.Right != nil { // Other one child case
    				cur.n = cur.n.Right
    			} else { // When we have no children, we need to break the fast loop and de-queue
    				break fast
    			}
    			cur.d++
    		}
    
    		// PopFront
    		if len(q) > 1 {
    			q = q[1:]
    		} else {
    			break all
    		}
    	}
    
    	return maxDepth
    }

Log in to reply
 

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