# 2022-05-30

## [82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)

### Description

Given the `head` of a sorted linked list, *delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list*. Return *the linked list **sorted** as well*.

**Example 1:**

![](https://img.content.cc/a/2022/05/30/09-39-04-987-660f952a3b16aa11de97081f306cf666-c03202.jpeg)

```
Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]
```

**Example 2:**

![](https://img.content.cc/a/2022/05/30/09-39-20-908-e5ea2dae9e9a33fea2ef4d8acf2289a0-c8e5e7.jpeg)

```
Input: head = [1,1,1,2,3]
Output: [2,3]
```

**Constraints:**

* The number of nodes in the list is in the range `[0, 300]`.
* `-100 <= Node.val <= 100`
* The list is guaranteed to be **sorted** in ascending order.

### Solution

#### Approach #0

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteDuplicates(head *ListNode) *ListNode {
    return dfs(head, -101)
}

func dfs(cur *ListNode, val int) *ListNode {
    if cur == nil {
        return nil
    }
    if cur.Val == val || (cur.Next != nil && cur.Next.Val == cur.Val) {
        return dfs(cur.Next, cur.Val)
    }
    cur.Next = dfs(cur.Next, cur.Val)
    return cur
}
```

#### Approach #1

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteDuplicates(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }
    newHead := &ListNode{Next: head}
    cur := newHead
    for cur.Next != nil && cur.Next.Next != nil {
        if cur.Next.Val == cur.Next.Next.Val {
            v := cur.Next.Val
            for cur.Next != nil && cur.Next.Val == v {
                cur.Next = cur.Next.Next
            }
        } else {
            cur = cur.Next
        }
    }
    return newHead.Next
}
```

## [15. 3Sum](https://leetcode.com/problems/3sum/)

### Description

Given an integer array nums, return all the triplets `[nums[i], nums[j], nums[k]]` such that `i != j`, `i != k`, and `j != k`, and `nums[i] + nums[j] + nums[k] == 0`.

Notice that the solution set must not contain duplicate triplets.

**Example 1:**

```
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
```

**Example 2:**

```
Input: nums = []
Output: []
```

**Example 3:**

```
Input: nums = [0]
Output: [] 
```

**Constraints:**

* `0 <= nums.length <= 3000`
* `-10^5 <= nums[i] <= 10^5`

### Solution

#### Approach #0

```go
func threeSum(nums []int) [][]int {
    sort.Ints(nums)
    n := len(nums)
    var res [][]int
    for i := 0; i < n; i++ {
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }
        k := n - 1
        for j := i + 1; j < n; j++ {
            if j > i+1 && nums[j] == nums[j-1] {
                continue
            }
            for j < k && nums[i]+nums[j]+nums[k] > 0 {
                k--
            }
            if j == k {
                break
            }
            if nums[i]+nums[j]+nums[k] == 0 {
                res = append(res, []int{nums[i], nums[j], nums[k]})
            }
        }
    }
    return res
}
```

## [1022. Sum of Root To Leaf Binary Numbers](https://leetcode.com/problems/sum-of-root-to-leaf-binary-numbers/)

### Description

You are given the `root` of a binary tree where each node has a value `0` or `1`. Each root-to-leaf path represents a binary number starting with the most significant bit.

* For example, if the path is `0 -> 1 -> 1 -> 0 -> 1`, then this could represent `01101` in binary, which is `13`.

For all leaves in the tree, consider the numbers represented by the path from the root to that leaf. Return *the sum of these numbers*.

The test cases are generated so that the answer fits in a **32-bits** integer.

**Example 1:**

![](https://img.content.cc/a/2022/05/30/14-30-21-934-36029c6aea051f3a535267cd23ce9342-6f931c.png)

```
Input: root = [1,0,1,0,1,0,1]
Output: 22
Explanation: (100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22
```

**Example 2:**

```
Input: root = [0]
Output: 0 
```

**Constraints:**

* The number of nodes in the tree is in the range `[1, 1000]`.
* `Node.val` is `0` or `1`.

### Solution

#### Approach #0

```go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumRootToLeaf(root *TreeNode) int {
    return sum(root, 0)
}

func sum(node *TreeNode, num int) int {
    if node.Left != nil && node.Right != nil {
        return sum(node.Left, num<<1+node.Val) + sum(node.Right, num<<1+node.Val)
    }
    if node.Left != nil {
        return sum(node.Left, num<<1+node.Val)
    }
    if node.Right != nil {
        return sum(node.Right, num<<1+node.Val)
    }
    return num<<1 + node.Val
}
```

#### Approach #1

```go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumRootToLeaf(root *TreeNode) int {
    var val, res int
    var stack []*TreeNode
    var pre *TreeNode
    for root != nil || len(stack) > 0 {
        for root != nil {
            val = val<<1 | root.Val
            stack = append(stack, root)
            root = root.Left
        }
        root = stack[len(stack)-1]
        if root.Right == nil || root.Right == pre {
            if root.Left == nil && root.Right == nil {
                res = res + val
            }
            val = val >> 1
            stack = stack[:len(stack)-1]
            pre = root
            root = nil
        } else {
            root = root.Right
        }
    }
    return res
}
```