Swift solution - DFS with HashMap


  • 0
    class Solution {
        func rob(_ root: TreeNode?) -> Int {
            var cache = [TreeNode: Int]()
            var root = root
            
            return helper(&root, &cache)
        }
        
        func helper(_ root: inout TreeNode?, _ cache: inout [TreeNode: Int]) -> Int {
            guard let root = root else {
                return 0
            }
            
            if let cacheValue = cache[root] {
                return cacheValue
            }
            
            var val = root.val
            
            if let leftNode = root.left {
                val += (helper(&leftNode.left, &cache) + helper(&leftNode.right, &cache))
            }
            if let rightNode = root.right {
                val += (helper(&rightNode.left, &cache) + helper(&rightNode.right, &cache))
            }
            
            val = max(val, helper(&root.left, &cache) + helper(&root.right, &cache))
            cache[root] = val
            
            return val
        }
    }
    
    extension TreeNode: Equatable {
        public static func == (_ lhs: TreeNode, _ rhs: TreeNode) -> Bool {
            return lhs.val == rhs.val
        }
    }
    
    extension TreeNode: Hashable {
        public var hashValue: Int {
            return val
        }
    }
    

Log in to reply
 

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