https://leetcode.com/problems/merge-two-binary-trees/

1. Use recursion:

  1. //44 ms    21.9 MB
  3. /**
  4.  * Definition for a binary tree node.
  5.  * struct TreeNode {
  6.  *     int val;
  7.  *     TreeNode *left;
  8.  *     TreeNode *right;
  9.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  10.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  11.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  12.  * };
  13.  */
  14. class Solution {
  15. public:
  16.     TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
  17.         if(!t1 && !t2)
  18.             return NULL;
  20.         if(t1 && t2){  //if both t1 and t2 exist
  21.             t1->val = t1->val + t2->val;
  22.             t1->left = mergeTrees(t1->left, t2->left);
  23.             t1->right = mergeTrees(t1->right, t2->right);
  24.         } else if(t1 && !t2){  //if only current t2 is empty
  25.             return t1;
  26.         } else if(!t1 && t2){  //if only current t1 is empty
  27.             return t2;
  28.         }
  30.         return t1;
  31.     }
  32. };

Time Complexity : O(m)
Space Complexity : O(m)
m = the minimum number of nodes from the two given trees