AlgoExpert Practice (BST, Binary Tree, Linked Lists)

func isValidBST(root *TreeNode) bool {
    return rec(root, -1<<63, 1<<63-1)
}

func rec(node *TreeNode, min, max int)bool{
    if node == nil{
        return true
    }
    v := node.Val
    return v >= min && v < max &&
        rec(node.Left, min, v) &&
            rec(node.Right, v, max)
}

func maxPathSum(root *TreeNode) int {
    ans := -1<<31
    rec(root, &ans)
    return ans
}

func rec(node *TreeNode, ans *int)int{
    if node == nil{
        return 0
    }
    v := node.Val
    leftSumAsBranch := rec(node.Left, ans)
    rightSumAsBranch := rec(node.Right, ans)
    // 答案的路径一定可以表示成leftSumAsBranch + v + rightSumAsBranch的形式
    *ans = max(*ans, leftSumAsBranch+v+rightSumAsBranch)
    // 为负数时返回0，不计入路径
    sumAsBranch := max(max(leftSumAsBranch+v, rightSumAsBranch+v), 0)
    return sumAsBranch
}

type LRUCache struct {
    cap int
    Keys map[int]*Node
    Dummy *Node
}

type Node struct{
    Key, Value int
    Pre, Next *Node
}

func Constructor(capacity int) LRUCache {
    dum := new(Node)
    dum.Pre = dum
    dum.Next = dum
    return LRUCache{
        cap: capacity,
        Keys: map[int]*Node{},
        Dummy: dum,
    }
}

func (c *LRUCache) Get(key int) int {
   if node, ok := c.Keys[key]; ok{
       rmFromList(c, node)
       addToList(c, node)
       return node.Value
   }
    return -1
}

func (c *LRUCache) Put(key int, value int)  {
    if node, ok := c.Keys[key]; ok{
       rmFromList(c, node)
       node.Value = value
       addToList(c, node)
       return
   }

   node := &Node{Key: key, Value:value}
   c.Keys[key] = node
   addToList(c, node)

   if len(c.Keys) > c.cap{
       delete(c.Keys, c.Dummy.Pre.Key)
       rmFromList(c, c.Dummy.Pre)
   }
}

func addToList(c *LRUCache, node *Node){
    node.Pre = c.Dummy
    node.Next = c.Dummy.Next
    node.Pre.Next = node
    node.Next.Pre = node
}

func rmFromList(c *LRUCache, node *Node){
    node.Pre.Next = node.Next
    node.Next.Pre = node.Pre
}