Code & Func

第54天。

今天的题目是All Elements in Two Binary Search Trees:

先用先序遍历拿到每棵树上的值，因为是二叉搜索树，所以先序得到的就是有序的值，所以做一次归并即可：

1
vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
2
    vector<int> left;
3
    vector<int> right;
4
    getAllElements(root1, left);
5
    getAllElements(root2, right);
6

7
    int len = left.size() + right.size();
8
    if (len == 0) return vector<int>();
9
    vector<int> vec(len);
10

11
    int i = 0, j = 0, k = 0;
12
    while(i < left.size() && j < right.size()) {
13
        if (left[i] < right[j]) vec[k++] = left[i++];
14
        else vec[k++] = right[j++];
15
    }
22 collapsed lines
16
    while(i < left.size()) vec[k++] = left[i++];
17
    while(j < right.size()) vec[k++] = right[j++];
18
    return vec;
19

20
}
21

22

23
void getAllElements(TreeNode *root, vector<int> &vec) {
24
    if (root == nullptr) return ;
25
    stack<TreeNode *> st;
26
    while(root || !st.empty()) {
27
        while(root) {
28
            st.push(root);
29
            root = root->left;
30
        }
31
        if (!st.empty()) {
32
            root = st.top(); st.pop();
33
            vec.push_back(root->val);
34
            root = root->right;
35
        }
36
    }
37
}