Go O(n) DFS, one-liner Abs trick


  • 0
    A
    func findTilt(root *TreeNode) int {
    	totalTilt := 0
    
    	var treeSum func(*TreeNode) int
    	treeSum = func(n *TreeNode) int {
    		if n == nil {
    			return 0
    		}
    
    		l, r := treeSum(n.Right), treeSum(n.Left) // DF traveral
    		tilt := l - r
    		tilt += tilt >> 64 * 2 * tilt // Abs
    		totalTilt += tilt             // Update the global tilt
    		return l + r + n.Val          // Return the total depth
    	}
    
    	treeSum(root)
    	return totalTilt
    }

Log in to reply
 

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