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;
}

vector<vector<int>> visited;
void dfs(vector<vector<int>> &grid, int x, int y) {
    static int dx[] = {-1, 0, 1, 0};
    static int dy[] = {0, 1, 0, -1};
    visited[x][y] = true; // 标记已访问
    for(int i = 0; i < 4; i++) { // 遍历上下左右邻接点
        int tx = x + dx[i];
        int ty = y + dy[i];
        if(tx < 0 || ty < 0 || tx >= grid.size() || ty >= grid[0].size() || visited[tx][ty]) {
            continue; // 出界或已访问过
        } else {
            dfs(grid, tx, ty);
        }
    }
}

vector<int> visited;
void bfs(vector<vector<int>> &graph, int start) {
    queue<int> q;
    q.push(start);
    visited[start] = 1;
    
    while(!q.empty()) {
        int size = q.size();
        while(size-- > 0) {
            int cur = q.front(); q.pop();
            visited[cur] = 1;
            for(auto next : graph[cur]) {
                if(!visited[next]) {
                    q.push(next);
                    visited[next] = 1;
                }
            }
        }
    }
}

ListNode* reverseList(ListNode* head) {
	if(!head || !(head->next)) {
		return head;
	}
	ListNode *pre = head;
	ListNode *p = head->next;
	ListNode *next = NULL;
	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);
}