五一假期快乐!还是要按时刷题
题目描述
题目链接,1305. 两棵二叉搜索树中的所有元素,题目截图如下:
题目分析
这道题十分的中规中矩,放在五月的第一天,倒也非常适合。题目意思就是,给你两个二叉搜索树,然后你需要返回一个列表,列表中的元素按照升序进行排列。
我们知道二叉搜索树,其中序遍历(左根右)就是升序排列的,因为二叉搜索树其左节点数值小于根节点的数值,而根节点的数值小于右节点的数值。那么我们按照左根右的顺序遍历树,就能够得到一个升序的数组了。
既然如此,那我们的思路就出来了,首先对两个二叉搜索树进行中序遍历,得到两个升序数组,之后我们再对这个两个升序数组进行排序即可。
代码实现
c++代码实现如下所示:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
vector<int> left;
vector<int> right;
vector<int> res;
midOrder(root1,left);
midOrder(root2,right);
int l_n = left.size(),r_n = right.size();
int l = 0,r = 0;
while(l<l_n && r<r_n){
if(left[l]<right[r]){
res.push_back(left[l++]);
}else{
res.push_back(right[r++]);
}
}
while(l<l_n){
res.push_back(left[l++]);
}
while(r<r_n){
res.push_back(right[r++]);
}
return res;
}
void midOrder(TreeNode* root,vector<int> &res){
// 二叉搜索树的中序遍历
if(root==NULL){
return;
}
midOrder(root->left,res);
res.push_back(root->val);
midOrder(root->right,res);
}
};
结语
每天进步一点点,offer就近一点点。
Q.E.D.