LeetCode合并二叉树

　　方法一：深度优先搜索
　　从根节点开始同时遍历两个二叉树，并将对应的节点进行合并。两个二叉树的对应节点可能存在三种情况，对于每种情况使用不同的合并方式
　　1、如果两个二叉树对应节点都为空，则合并后的二叉树的对应节点也为空
　　2、如果两个二叉树的对应节点只有一个为空，则合并后的二叉树的对应节点为其中的非空节点
　　3、如果两个二叉树的对应节点都不为空，则合并后的二叉树的对应节点的值为两个二叉树的对应节点的值之和
　　4、对一个结点进行合并之后，还要对该节点的左右子树分别进行合并，这是一个递归的过程struct TreeNode {      int val;      struct TreeNode *left;      struct TreeNode *right; }; struct TreeNode* mergeTrees(struct TreeNode* root1, struct TreeNode* root2) {     if(!root1 && !root2) return NULL;     if(root1 && !root2) return root1;     if(!root1 && root2) return root2;     root1->left = mergeTrees(root1->left, root2->left);     root1->right = mergeTrees(root1->right, root2->right);     root1->val = root1->val + root2->val;     return root1; }
　　方法二、广度优先搜索 struct TreeNode* mergeTrees(struct TreeNode* t1, struct TreeNode* t2) {     if (t1 == NULL) {         return t2;     }     if (t2 == NULL) {         return t1;     }     struct TreeNode* merged = malloc(sizeof(struct TreeNode));     merged->val = t1->val + t2->val;     struct TreeNode** q = malloc(sizeof(struct TreeNode*) * 2001);     struct TreeNode** queue1 = malloc(sizeof(struct TreeNode*) * 2001);     struct TreeNode** queue2 = malloc(sizeof(struct TreeNode*) * 2001);     int qleft = 0, qright = 0;     q[qright] = merged;     queue1[qright] = t1;     queue2[qright] = t2;     qright++;     while (qleft < qright) {         struct TreeNode *node = q[qleft], *node1 = queue1[qleft], *node2 = queue2[qleft];         qleft++;         struct TreeNode *left1 = node1->left, *left2 = node2->left, *right1 = node1->right, *right2 = node2->right;         if (left1 != NULL || left2 != NULL) {             if (left1 != NULL && left2 != NULL) {                 struct TreeNode* left = malloc(sizeof(struct TreeNode));                 left->val = left1->val + left2->val;                 node->left = left;                 q[qright] = left;                 queue1[qright] = left1;                 queue2[qright] = left2;                 qright++;             } else if (left1 != NULL) {                 node->left = left1;             } else if (left2 != NULL) {                 node->left = left2;             }         } else {             node->left = NULL;         }         if (right1 != NULL || right2 != NULL) {             if (right1 != NULL && right2 != NULL) {                 struct TreeNode* right = malloc(sizeof(struct TreeNode));                 right->val = right1->val + right2->val;                 node->right = right;                 q[qright] = right;                 queue1[qright] = right1;                 queue2[qright] = right2;                 qright++;             } else if (right1 != NULL) {                 node->right = right1;             } else {                 node->right = right2;             }         } else {             node->right = NULL;         }     }     return merged; }