# Delete Nodes And Return Forest

Given the `root` of a binary tree, each node in the tree has a distinct value.

After deleting all nodes with a value in `to_delete`, we are left with a forest (a disjoint union of trees).

Return the roots of the trees in the remaining forest.  You may return the result in any order.

Example 1:

```Input: root = [1,2,3,4,5,6,7], to_delete = [3,5]
Output: [[1,2,null,4],,]
```

Constraints:

• The number of nodes in the given tree is at most `1000`.
• Each node has a distinct value between `1` and `1000`.
• `to_delete.length <= 1000`
• `to_delete` contains distinct values between `1` and `1000`.
```# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def delNodes(self, root, to_delete):
"""
:type root: TreeNode
:type to_delete: List[int]
:rtype: List[TreeNode]
"""
self.forests = []
self.delete = to_delete

node = self.divideAndConquer(root)

if node:
self.forests.append(node)

return self.forests

def divideAndConquer(self, node):

if not node:
return None

left = self.divideAndConquer(node.left)
right = self.divideAndConquer(node.right)

if node.val not in self.delete:
node.left = left
node.right = right
return node
else:
if left:
self.forests.append(left)
if right:
self.forests.append(right)

return None```

# Union-Find Python Implementation

```class UF:
def __init__(self, n):
self.p = list(range(n))

def union(self, x, y):
self.p[self.find(x)] = self.find(y)

def find(self, x):
if x != self.p[x]:
self.p[x] = self.find(self.p[x])
return self.p[x]```

# Minimum Knight Moves

In an infinite chess board with coordinates from `-infinity` to `+infinity`, you have a knight at square `[0, 0]`.

A knight has 8 possible moves it can make, as illustrated below. Each move is two squares in a cardinal direction, then one square in an orthogonal direction.

Return the minimum number of steps needed to move the knight to the square `[x, y]`.  It is guaranteed the answer exists.

Example 1:

```Input: x = 2, y = 1
Output: 1
Explanation: [0, 0] → [2, 1]
```

Example 2:

```Input: x = 5, y = 5
Output: 4
Explanation: [0, 0] → [2, 1] → [4, 2] → [3, 4] → [5, 5]```
```class Solution:
def minKnightMoves(self, x: int, y: int) -> int:
x, y = abs(x), abs(y)

q = collections.deque([(0,0,0)])
seen = set([(0,0)])

while q:
s_x, s_y, s = q.popleft()
if (s_x, s_y) == (x,y):
return s

d = []
for dx, dy in [(-2,-1),(-2,1),(-1,2),(1,2),(2,1),(2,-1),(1,-2),(-1,-2)]:
n_x = s_x + dx
n_y = s_y + dy
if -2 <= n_x <= x and -2 <= n_y <= y:
d.append((n_x,n_y))

d.sort(key=lambda e: abs(x-e) + abs(y-e))

# only enqueue towards the 2 directions closest to the x,y
for n_x,n_y in d[:2]:
if (n_x, n_y) not in seen:
q.append((n_x,n_y,s+1))

# Sum Root to Leaf Numbers

Given a binary tree containing digits from `0-9` only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path `1->2->3` which represents the number `123`.

Find the total sum of all root-to-leaf numbers.

Note: A leaf is a node with no children.

Example:

```Input: [1,2,3]
1
/ \
2   3
Output: 25
Explanation:
The root-to-leaf path `1->2` represents the number `12`.
The root-to-leaf path `1->3` represents the number `13`.
Therefore, sum = 12 + 13 = `25`.```

Example 2:

```Input: [4,9,0,5,1]
4
/ \
9   0
/ \
5   1
Output: 1026
Explanation:
The root-to-leaf path `4->9->5` represents the number 495.
The root-to-leaf path `4->9->1` represents the number 491.
The root-to-leaf path `4->0` represents the number 40.
Therefore, sum = 495 + 491 + 40 = `1026`.```
```# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def sumNumbers(self, root: TreeNode) -> int:
def getNumbers(root, previous, result):
if not root:
return

current = previous*10 + root.val

if not root.left and not root.right:
result += current

getNumbers(root.left, current, result)
getNumbers(root.right, current, result)

ans = 
getNumbers(root, 0, ans)
return ans ```

# Decode ways

A message containing letters from `A-Z` is being encoded to numbers using the following mapping:

```'A' -> 1
'B' -> 2
...
'Z' -> 26
```

Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

```Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).
```

Example 2:

```Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).```
```class Solution:
def numDecodings(self, s: str) -> int:
if s == '0': return 0

#         N = len(s)
#         dp = [1 for i in range(N+1)]

for i in range(1, len(s)):
if s[i] == '0':
# dp[i] = 0
b = 0
if int(s[i-1:i+1]) <= 26:
# dp[i+1] = dp[i] + dp[i-1]
c = b+a
else:
# dp[i+1] = dp[i]
c = b
a=b
b=c

return dp[-1]```

# Unique Binary Search Trees II

Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1 … n.

Example:

```Input: 3
Output:
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
Explanation:
The above output corresponds to the 5 unique BST's shown below:

1         3     3      2      1
\       /     /      / \      \
3     2     1      1   3      2
/     /       \                 \
2     1         2                 3```
```# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
from functools import lru_cache

class Solution:
def generateTrees(self, n):
if n == 0: return []

@lru_cache(maxsize=None)
def generate(start, end):
ans = []

if start > end: return [None]

for i in range(start, end+1):
for left_node in generate(start, i-1):
for right_node in generate(i+1, end):
node = TreeNode(i)
node.left = left_node
node.right = right_node
ans.append(node)

return ans

return generate(1, n)```

# 2 Keys Keyboard

Initially on a notepad only one character ‘A’ is present. You can perform two operations on this notepad for each step:

1. `Copy All`: You can copy all the characters present on the notepad (partial copy is not allowed).
2. `Paste`: You can paste the characters which are copied last time.

Given a number `n`. You have to get exactly `n` ‘A’ on the notepad by performing the minimum number of steps permitted. Output the minimum number of steps to get `n` ‘A’.

Example 1:

```Input: 3
Output: 3
Explanation:
Intitally, we have one character 'A'.
In step 1, we use Copy All operation.
In step 2, we use Paste operation to get 'AA'.
In step 3, we use Paste operation to get 'AAA'.
```

Note:

1. The `n` will be in the range [1, 1000].
```from functools import lru_cache

class Solution:
def minSteps(self, n: int) -> int:

#         @lru_cache(None)
#             if len(current) <= n:
#                 if len(current) == n:
#                     return 0

#                 t1 = (operation(current, current) if not notepad else 0x7777777) + 1

#                 t3 = (operation(current, current) if notepad and notepad != current else 0x7777777) + 1

#                 return min(t1, t2, t3)

#             else:
#                 return 0x7777777

#         result = operation(0, "A")

#         return result

if n == 1:
return 0

for i in range(2,n+1):
if n % i == 0:
return i + self.minSteps(int(n/i))
```

# Find K-th Palindrome Number of N Digits

Given N and K, output K-th Palindrome that has N digits.

Input: N = 2, K = 3
Output: [3, 3]
Explanation: [1,1] => [2,2] => [3, 3]

Input: N = 3, K = 5
Output: [1, 4, 1]
Explanation: [1, 0, 1] => [1, 1, 1] => [1, 2, 1] => [1, 3, 1] => [1, 4, 1]

Input: N = 5, K = 201
Output: [3, 0, 0, 0, 3]
Explanation: … => [2, 9, 8, 9, 2] => [2, 9, 9, 9, 2] => [3, 0, 0, 0, 3]

```def func(n, k, ans):
if n > 0:
segment = 10 ** ((n - 1) // 2)
element, next_k = divmod(k, segment)
ans.append(element)
func(n - 2, next_k, ans)

def generate(n, k):
ans = []
func(n, k - 1, ans)

ans += 1

if n % 2:
return ans[:-1] + ans[::-1]
else:
return ans + ans[::-1]

if __name__ == "__main__":
result = generate(5, 201)
print(result)```