2022/5/1力扣每日一题（1305. 两棵二叉搜索树中的所有元素）

题目详见力扣。

• 自己需要记录的知识点：

1. 二叉搜索树

• 当前节点的左子树中的数均小于当前节点的数；
• 当前节点的右子树中的数均大于当前节点的数；
• 所有左子树和右子树自身也是二叉搜索树。

2. 中序遍历

• 自己知道中序遍历是什么意思，但自己去写代码时还是不会写，就是不知道如何下手，有些无措，可能自己还是需要大量的积累。下面是官方的中序遍历代码（C++）：

void inorder(TreeNode *node, vector<int> &res) {
    if (node) {
        inorder(node->left, res);
        res.push_back(node->val);
        inorder(node->right, res);
    }
}

• 作者：LeetCode-Solution
• 链接：https://leetcode-cn.com/problems/all-elements-in-two-binary-search-trees/solution/liang-ke-er-cha-sou-suo-shu-zhong-de-suo-you-yua-3/
• 来源：力扣（LeetCode）

3. 归并排序

• 可以使用双指针方法合并两个有序数组。新开辟一个数组空间，将需要合并排序的两个有序数组看作两个队列，每次从队列头部取出比较小的数字放到结果中（头部相同时可任取一个）。下面是官方代码（C++）：

public:
    vector<int> getAllElements(TreeNode *root1, TreeNode *root2) {
        vector<int> nums1, nums2;
        inorder(root1, nums1);
        inorder(root2, nums2);

        vector<int> merged;
        auto p1 = nums1.begin(), p2 = nums2.begin();
        while (true) {
            if (p1 == nums1.end()) {
                merged.insert(merged.end(), p2, nums2.end());
                break;
            }
            if (p2 == nums2.end()) {
                merged.insert(merged.end(), p1, nums1.end());
                break;
            }
            if (*p1 < *p2) {
                merged.push_back(*p1++);
            } else {
                merged.push_back(*p2++);
            }
        }
        return merged;
    }

• 作者：LeetCode-Solution
• 链接：https://leetcode-cn.com/problems/all-elements-in-two-binary-search-trees/solution/liang-ke-er-cha-sou-suo-shu-zhong-de-suo-you-yua-3/
• 来源：力扣（LeetCode）

4. insert函数

• 待补充

5. vector

• 待补充