int binary_search(int a[], int n, int val) {
    int ret = -1; // 查找失败返回-1
    int left = 0;
    int right = n - 1;
    int mid;
    while(left <= right) {
        mid = left + (right - left) / 2; // 防止直接平均可能的溢出问题
        if(a[mid] < val) {
            left = mid + 1;
        } else if(a[mid] > val) {
            right = mid - 1;
        } else { // 相等情况放到最后，减少分支预测，因为多数搜索情况不是大于就是小于
            ret = mid;
            break;
        }
    }
    return ret;
}

sum[x][y] = grid[x][y] + sum[x-1][y] + sum[x][y-1] - sum[x-1][y-1]
area(x1,y1,x2,y2) = sum[x2][y2] - sum[x2][y1-1] - sum[x1-1][y2] + sum[x1-1][y1-1]

#define MAXN 1005

int G[MAXN][MAXN];  // 邻接矩阵
int n;              // 顶点数
bool visited[MAXN]; // 记录顶点是否已访问

void DFS_AM(int u) {
    cout << u << " ";
    visited[u] = true;
    for(int i = 0; i < n; i++) {
        if(G[u][i] && !visited[i]) {
            DFS_AM(i);
        }
    }
}

void BFS_AM(int u) {
    queue<int> Q;
    cout << u << " ";
    visited[u] = true;
    Q.push(u);
    while(!Q.empty()) {
        int v = Q.front();
        Q.pop();
        for(int i = 0; i < n; i++) { // 依次检查v的所有邻接点
            if(G[v][i] && !visited[i]) { // v、i相邻且i未被访问
                cout << i << " ";
                visited[i] = true;
                Q.push(i);
            }
        }
    }
}

#define MAXN 1000

vector<int> G[MAXN]; // 邻接表
int n;               // 顶点数
bool visited[MAXN];  // 记录顶点是否已访问

void DFS_AL(int u) {
    cout << u << " ";
    visited[u] = true;
    for(auto &i : G[u]) {
        if(!visited[i]) {
            DFS_AL(i);
        }
    }
}

void BFS_AL(int u) {   // 邻接表BFS，起点为u
    queue<int> Q;
    cout << u << " ";
    visited[u] = true;
    Q.push(u);
    while(!Q.empty()) {
        int v = Q.front();
        Q.pop();
        for(auto &i : G[v]) { // 依次检查v的所有邻接点
            if(!visited[i]) {
                cout << i << " ";
                visited[i] = true;
                Q.push(i);
            }
        }
    }
}

ListNode* reverseList(ListNode* head) {
	if(!head || !(head->next)) {
		return head;
	}
	ListNode *pre = head;
	ListNode *p = head->next;
	ListNode *next;
	while(p) {
		next = p->next;
		p->next = pre;
		pre = p;
		p = next;
	}
	head->next = nullptr;
	return pre;
}

void collect(TreeNode *root, int d) {
	if(root == nullptr || d < 0) {
		return;
	}
	if(d == 0) {
		ans.push_back(root->val);
	}
	collect(root->left, d - 1);
	collect(root->right, d - 1);
}