LeetCode-1305. All Elements in Two Binary Search Trees

LeetCode-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​​[-10^5, 10^5]​​.

题解：

/** * 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 {public: void getNum(TreeNode * &root, vector &v) { if (root != NULL) { getNum(root->left, v); v.push_back(root->val); getNum(root->right, v); } } vector getAllElements(TreeNode* root1, TreeNode* root2) { vector a, b, res; getNum(root1, a); getNum(root2, b); int l1 = a.size(), l2 = b.size(); int k1 = 0, k2 = 0; while (k1 != l1 && k2 != l2) { if (a[k1] < b[k2]) { res.push_back(a[k1++]); } else { res.push_back(b[k2++]); } } if (k1 == l1) { while (k2 != l2) { res.push_back(b[k2++]); } } if (k2 == l2) { while (k1 != l1) { res.push_back(a[k1++]); } } return res; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。