Swift 3 recursive method 42ms 100%


  • 0
    Y
    // tuple: .0 represents not rob current root, .1 rob current root
        func rob(_ root: TreeNode?) -> Int {
            guard let root = root else { return 0 }
            let ans = helper(root)
            return max(ans.0, ans.1)
        }
        
        func helper(_ root: TreeNode?) -> (Int, Int) {
            guard let root = root else {
                return (0, 0)
            }
            let left = helper(root.left)
            let right = helper(root.right)
            
            // not rob current house, max result of four different cases with/out left/right node
            let noCur = max(left.0, left.1) + max(right.0, right.1)
            // rob current house, so cannot rob left and right nodes
            let cur = left.0 + right.0 + root.val
            
            return (noCur, cur)
        }
    
    

Log in to reply
 

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