class Solution:
def sumZero(self, n: int) -> List[int]:
ans = []
if n & 1:
ans.append(0)
for i in range(1, n//2 + 1):
ans.append(i)
ans.append(-i)
return ans


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:
ans = []

def dfs(root):
if not root:
return
ans.append(root.val)
dfs(root.left)
dfs(root.right)

dfs(root1)
dfs(root2)

ans.sort()

return ans


class Solution:
def canReach(self, arr: List[int], start: int) -> bool:
if arr[start] == 0:
return True
n = len(arr)
visited = set()
stack = [start]

while stack:
x = stack.pop()
for y in [x + arr[x], x - arr[x]]:
if 0 <= y < n and y not in visited:
if arr[y] == 0:
return True
stack.append(y)
return False


SEND + MORE = MONEY

1000S + 100E + 10N + D + 1000M + 100O + 10R + E - 10000M - 1000O - 100N - 10E - Y = 0，

1000S + 91E - 90N + D - 9000M - 900O + 10R - Y = 0.

int get_multiplier(int *mult, int *nonzero, char *word, int p) {
int n = strlen(word);
char *str = word + n;
while (str != word) {
str --;
int idx = *str - 'A';
if (str == word)
nonzero[idx] = 1;
mult[idx] += p;
p *= 10;
}
return 0;
}

int dfs(int *low, int *high, int *vals, int n, int i, int cur, int used, bool *ret) {
if (*ret)
return 0;
if (i == n) {
if (cur == 0)
*ret = true;
return 0;
}
for (int d = low[i]; d <= high[i]; d ++) {
if ((used >> d) & 1)
continue;
dfs(low, high, vals, n, i+1, cur+d*vals[i], used|(1<<d), ret);
}
return 0;
}

bool isSolvable(char ** words, int wordsSize, char * result){
int mult[26] = {0};
int nonzero[26] = {0};
int n = 0;
int vals[26];
int low[26];
int high[26];
bool ret = false;
for (int i = 0; i < wordsSize; i ++)
get_multiplier(mult, nonzero, words[i], 1);
get_multiplier(mult, nonzero, result, -1);
for (int i = 0; i < 26; i ++)
if (mult[i] != 0) {
vals[n] = mult[i];
low[n] = 0;
high[n] = 9;
if (nonzero[i])
low[n] = 1;
n ++;
}
if (n > 10)
return false;

// 以下这段是优化，使用之后能使运行时间从 ～550ms 减到 ～250ms
/*
int m = 0;
for (int i = 0; i < n; i ++)
if (vals[i] > vals[m])
m = i;
if (vals[m] < 0)
return false;
int s = 0;
for (int i = 0; i < n; i ++)
if (vals[i] < 0)
s -= vals[i];
int t = 0;
for (int i = 0; i < n; i ++)
if (i != m && vals[i] > 0)
t += vals[i];
if (1 + (9 * s - t) / vals[m] < high[m])
high[m] = 1 + (9 * s - t) / vals[m];
if ((s - 9 * t) / vals[m] > low[m])
low[m] = (s - 9*t) / vals[m];

for (int i = 0; i < n; i ++)
if (vals[i] < vals[m])
m = i;
if (vals[m] > 0)
return false;
s = 0;
for (int i = 0; i < n; i ++)
if (vals[i] > 0)
s += vals[i];
t = 0;
for (int i = 0; i < n; i ++)
if (i != m && vals[i] < 0)
t -= vals[i];
if (1 + (9 * s - t) / (-vals[m]) < high[m])
high[m] = 1 + (9 * s - t) / (-vals[m]);
if ((s - 9 * t) / (-vals[m]) > low[m])
low[m] = (s - 9*t) / (-vals[m]);
*/

dfs(low, high, vals, n, 0, 0, 0, &ret);
return ret;
}