仅供自己学习
思路:
因为两棵树都是二叉搜索树,所以我们直接中序遍历获得从小到大排序好的一个vector,然后在进行归并排序即可。
将树转为vector用的模板的中序遍历即可。
对于归并排序一个while循环,加入的条件是 i<r1.size()&& (r1[i]<=r2[j] || j==r2.size())),则当一个数组遍历完后,另一个数组还没有遍历完成也能直接加入res的数组中
代码:
1 /** 2 * Definition for a binary tree node. 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */ 10 class Solution { 11 public: 12 void LDR(TreeNode* root,vector<int>& s){ 13 if(root==NULL) return; 14 if(root->left)LDR(root->left,s); 15 s.push_back(root->val); 16 if(root->right)LDR(root->right,s); 17 } 18 vector<int> getAllElements(TreeNode* root1, TreeNode* root2) { 19 vector<int> r1,r2; 20 vector<int> res; 21 LDR(root1,r1); 22 LDR(root2,r2); 23 int i=0,j=0; 24 while(i<r1.size()||j<r2.size()){ 25 if(i<r1.size()&&(j==r2.size()||r1[i]<=r2[j])) { 26 res.push_back(r1[i++]); 27 } 28 else { 29 res.push_back(r2[j++]); 30 } 31 } 32 return res; 33 } 34 35 };