1305. All Elements in Two Binary Search Trees**

Elements in Two Binary Search Trees**"/>

1305. All Elements in Two Binary Search Trees**

1305. All Elements in Two Binary Search Trees**

/

题目描述

Given two binary search trees root1 and root2.

Return a list containing all the integers from both trees sorted in ascending order.

Example 1:

Input: root1 = [2,1,4], root2 = [1,0,3]
Output: [0,1,1,2,3,4]

Example 2:

Input: root1 = [0,-10,10], root2 = [5,1,7,0,2]
Output: [-10,0,0,1,2,5,7,10]

Example 3:

Input: root1 = [], root2 = [5,1,7,0,2]
Output: [0,1,2,5,7]

Example 4:

Input: root1 = [0,-10,10], root2 = []
Output: [-10,0,10]

Example 5:

Input: root1 = [1,null,8], root2 = [8,1]
Output: [1,1,8,8]

Constraints:

• Each tree has at most 5000 nodes.
• Each node’s value is between [ − 1 0 5 , 1 0 5 ] [-10^5, 10^5] [−105,105].

C++ 实现 1

杨千嬅的 <处处吻> 也太好听了吧, 好燃!!! 让我产生了自己还可以刷 100 题的错觉 🤣🤣🤣🤣

对 BST 进行中序遍历, 得到的数组是有序的, 最后将两个有序数组进行合并. C++ 实现 1 给出用自己写的合并方法. C++ 实现 2 用标准库提供的 std::merge 就能更为简洁的实现.

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
private:void inorder(TreeNode *root, vector<int> &res) {if (!root) return;inorder(root->left, res);res.push_back(root->val);inorder(root->right, res);}
public:vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {vector<int> v1, v2, res;inorder(root1, v1);inorder(root2, v2);int i = 0, j = 0;while (i < v1.size() && j < v2.size()) {if (v1[i] < v2[j]) res.push_back(v1[i++]);else res.push_back(v2[j++]);}if (i < v1.size()) std::copy(v1.begin() + i, v1.end(), back_inserter(res));if (j < v2.size()) std::copy(v2.begin() + j, v2.end(), back_inserter(res));return res;}
};

C++ 实现 2

使用标准库提供的 std::merge() 方法, 将两个有序数组合并为一个有序数组.

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
private:void inorder(TreeNode *root, vector<int> &res) {if (!root) return;inorder(root->left, res);res.push_back(root->val);inorder(root->right, res);}
public:vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {vector<int> v1, v2;inorder(root1, v1);inorder(root2, v2);vector<int> res(v1.size() + v2.size());std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), res.begin());return res;}
};