Golang DFS solution (bottom up)


  • 0

    Clear explanation can be found here.
    For me, figuring out a bottom up recursive way was not easy level though...

    func isBalanced(root *TreeNode) bool {
    	_, ok := check(root)
    	return ok
    }
    
    // check checks the tree from a given parent and returns a height of the tree
    // if the tree is balanced. Otherwise return false as the second return value.
    func check(parent *TreeNode) (int, bool) {
    	if parent == nil {
    		return 0, true
    	}
    
    	l, ok := check(parent.Left)
    	if !ok {
    		return 0, false
    	}
    	r, ok := check(parent.Right)
    	if !ok {
    		return 0, false
    	}
    
    	if diff := abs(l - r); diff > 1 {
    		return 0, false
    	}
    	return max(l, r) + 1, true
    }
    
    func max(a, b int) int {
    	if a > b {
    		return a
    	}
    	return b
    }
    
    func abs(a int) int {
    	if a >= 0 {
    		return a
    	}
    	return -a
    }
    

Log in to reply
 

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