# 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 = [1,null,8], root2 = [8,1]
Output: [1,1,8,8]
``````

Constraints:

• The number of nodes in each tree is in the range `[0, 5000]`.
• `-10^5 <= Node.val <= 10^5`

``````class Solution {
public:
vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
vector<int> res;
dfs(root1, res);
dfs(root2, res);
sort(res.begin(), res.end());
return res;
}
void dfs(TreeNode* node, vector<int>& res) {
if (!node) return;
dfs(node->left, res);
res.push_back(node->val);
dfs(node->right, res);
}
};
``````

``````class Solution {
public:
vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
vector<int> res;
queue<int> q1, q2;
dfs(root1, q1);
dfs(root2, q2);
while (!q1.empty() || !q2.empty()) {
if (q2.empty() || (!q1.empty() && q1.front() <= q2.front())) {
res.push_back(q1.front());
q1.pop();
} else {
res.push_back(q2.front());
q2.pop();
}
}
return res;
}
void dfs(TreeNode* node, queue<int>& q) {
if (!node) return;
dfs(node->left, q);
q.push(node->val);
dfs(node->right, q);
}
};
``````

``````class Solution {
public:
vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
vector<int> res;
stack<TreeNode*> st1, st2;
while (root1 || root2 || !st1.empty() || !st2.empty()) {
while (root1) {
st1.push(root1);
root1 = root1->left;
}
while (root2) {
st2.push(root2);
root2 = root2->left;
}
if (st2.empty() || (!st1.empty() && st1.top()->val <= st2.top()->val)) {
root1 = st1.top(); st1.pop();
res.push_back(root1->val);
root1 = root1->right;
} else {
root2 = st2.top(); st2.pop();
res.push_back(root2->val);
root2 = root2->right;
}
}
return res;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1305

https://leetcode.com/problems/all-elements-in-two-binary-search-trees/

https://leetcode.com/problems/all-elements-in-two-binary-search-trees/discuss/1719941/C%2B%2B-oror-Best-Explanation-oror-Naive-and-Optimal

https://leetcode.com/problems/all-elements-in-two-binary-search-trees/discuss/1720210/JavaC%2B%2BPython-A-very-very-detailed-EXPLANATION

LeetCode All in One 题目讲解汇总(持续更新中…)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation