C++

1class Solution {
2  public:
3    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
4      if(!root1) return root2;
5      if(!root2) return root1;
6
7#if 1
8      // recursive
9      root1->val += root2->val;
10      root1->left = mergeTrees(root1->left, root2->left);
11      root1->right = mergeTrees(root1->right, root2->right);
12#endif
13
14#if 0
15      // iterative using a stack
16      stack<TreeNode *> s;
17      TreeNode *temp = new TreeNode(0);
18      TreeNode *n;
19      temp->left = root1;
20      temp->right = root2;
21      s.push(temp);
22
23      while(!s.empty()) {
24        n = s.top(); s.pop();
25        if(!n->left || !n->right) continue;
26        n->left->val += n->right->val;
27
28        if(n->left->left == nullptr) n->left->left = n->right->left;
29        else {
30          TreeNode *t = new TreeNode(0);
31          t->left = n->left->left;
32          t->right = n->right->left;
33          s.push(t);
34        }
35
36        if(n->left->right == nullptr) n->left->right = n->right->right;
37        else {
38          TreeNode *t = new TreeNode(0);
39          t->left = n->left->right;
40          t->right = n->right->right;
41          s.push(t);
42        }
43      }
44#endif
45      return root1;
46    }
47};