刷题牛客
求二叉树的层序遍历
https://www.nowcoder.com/practice/04a5560e43e24e9db4595865dc9c63a3
- 题号NC-15,二叉树的层序遍历
class Solution {
public:
/**
*
* @param root TreeNode类
* @return int整型vector<vector<>>
*/
vector<vector<int> > levelOrder(TreeNode* root) {
// write code here
queue<TreeNode*> q;
vector<vector<int>> res;
if(!root) return res; // 这个也会发生段错误
else q.push(root);
while (q.size() > 0) {
int s = q.size();
vector<int> temp;
for (int i = 0; i < s; i++) {
temp.push_back(q.front()->val);
if (q.front()->left != NULL) q.push(q.front()->left);
if (q.front()->right != NULL) q.push(q.front()->right);
q.pop();
}
res.push_back(temp);
}
return res;
}
};
- NC105:二分查找(迷之排序)https://www.nowcoder.com/practice/7bc4a1c7c371425d9faa9d1b511fe193
class Solution {
public:
/**
* 二分查找
* @param n int整型 数组长度
* @param v int整型 查找值
* @param a int整型vector 有序数组
* @return int整型
*/
int upper_bound_(int n, int v, vector<int>& a) {
// write code here
int left = 0, right = a.size() - 1;
while (left < right) {
int mid = left + right >> 1;
if(a[mid] >= v) {
right = mid;
} else {
left = mid+1;
}
}
if(a[right] >= v) return right + 1;
else return right + 2;
}
};