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;}
};
更多推荐
1305. All Elements in Two Binary Search Trees**
发布评论