leetcode

0 // Not using BST property at all

1 class Solution {

2 void travel(TreeNode *root, multiset<int> &s) {

3 stack<TreeNode *> st;

4 while (true) {

5 while (root) {

6 if (root->right) st.push(root->right);

7 s.insert(root->val);

8 root = root->left;

9 }

10 if (st.empty()) break;

11 root = st.top(), st.pop();

12 }

13 }

14

15 public:

16 vector<int> getAllElements(TreeNode *root1, TreeNode *root2) {

17 vector<int> res;

18 multiset<int> s;

19 travel(root1, s), travel(root2, s);

20 for (int n : s)

21 res.push_back(n);

22 return res;

23 }

24 };

25

26 // Using BST property to travel both trees in-order

27 class Solution {

28 void advance(TreeNode *root, stack<TreeNode *> &st) {

29 while (root) {

30 st.push(root);

31 root = root->left;

32 }

33 }

34

35 void append(vector<int> &res, stack<TreeNode *> &st) {

36 res.push_back(st.top()->val);

37 TreeNode *tmp = st.top();

38 st.pop();

39 advance(tmp->right, st);

40 }

41

42 public:

43 vector<int> getAllElements(TreeNode *root1, TreeNode *root2) {

44 stack<TreeNode *> st1, st2;

45 vector<int> res;

46 advance(root1, st1), advance(root2, st2);

47

48 while (!st1.empty() && !st2.empty()) {

49 if (st1.top()->val > st2.top()->val)

50 append(res, st2);

51 else

52 append(res, st1);

53 }

54 if (st1.empty()) std::swap(st1, st2);

55 while (!st1.empty())

56 append(res, st1);

57 return res;

58 }

59 };