第54天。
今天的题目是All Elements in Two Binary Search Trees:
先用先序遍历拿到每棵树上的值，因为是二叉搜索树，所以先序得到的就是有序的值，所以做一次归并即可：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
vector<int> left;
vector<int> right;
getAllElements(root1, left);
getAllElements(root2, right);
int len = left.size() + right.size();
if (len == 0) return vector<int>();
vector<int> vec(len);
int i = 0, j = 0, k = 0;
while(i < left.size() && j < right.size()) {
if (left[i] < right[j]) vec[k++] = left[i++];
else vec[k++] = right[j++];
}
while(i < left.size()) vec[k++] = left[i++];
while(j < right.size()) vec[k++] = right[j++];
return vec;
}
void getAllElements(TreeNode *root, vector<int> &vec) {
if (root == nullptr) return ;
stack<TreeNode *> st;
while(root || !st.empty()) {
while(root) {
st.push(root);
root = root->left;
}
if (!st.empty()) {
root = st.top(); st.pop();
vec.push_back(root->val);
root = root->right;
}
}
}
|