LeetCode617. 合并二叉树

题目

 1 class Solution {
 2 public:
 3     TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
 4         if(!t1 && !t2) return NULL;
 5         if(t1 == NULL&& t2 != NULL) return t2;
 6         if(t1 != NULL&& t2 == NULL) return t1;
 7         TreeNode* node = new TreeNode(t1->val + t2->val);;
 8         //指针赋值使用错误TreeNode* node; node->val = t1->val + t2->val;
 9         node->left = mergeTrees(t1->left,t2->left);
10         node->right = mergeTrees(t1->right,t2->right);
11         return node;
12     }
13 };

需要查看C++ primer, 复习指针使用

 1 class Solution {
 2 public:
 3     TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
 4         if(root1 == NULL) return root2;
 5         if(root2 == NULL) return root1;
 6         
 7         TreeNode *root = new TreeNode(root1->val + root2->val);
 8         root->left = mergeTrees(root1->left,root2->left);
 9         root->right = mergeTrees(root1->right,root2->right);
10         return root;
11 
12     }
13 };

迭代法层次遍历

 1 class Solution {
 2 public:
 3     TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
 4         if(root1 == NULL) return root2;
 5         if(root2 == NULL) return root1;
 6         
 7         //两个根都不为空
 8         queue<TreeNode*>que;
 9         que.push(root1);que.push(root2);
10         //TreeNode *node = new TreeNode;
11         while(!que.empty()){
12             auto t1 = que.front();que.pop();
13             auto t2 = que.front();que.pop();
14             t1->val +=  t2->val;
15             if(t1->left != NULL && t2->left != NULL){
16                 que.push(t1->left);
17                 que.push(t2->left);
18             }
19             if(t1->right != NULL && t2->right != NULL){
20                 que.push(t1->right);
21                 que.push(t2->right);
22             }
23             if(t1->left == NULL ){
24                 t1->left = t2->left;
25             }
26 
27             if(t1->right == NULL){
28                 t1->right = t2->right;
29             }
30         }
31         return root1;
32     }
33 };