题目描述
Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.
You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.
递归版本解题思路
- 每次new一个当前节点，负责存储左右节点的和
- 当前节点的左子树为，递归左子树。
- 反之亦然。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
if(t1 == NULL && t2 == NULL){
return NULL;
}
TreeNode* root;
if(t1 != NULL && t2 != NULL){
root = new TreeNode(t1 -> val + t2 -> val);
root -> left = mergeTrees(t1 -> left, t2 -> left);
root -> right = mergeTrees(t1 -> right, t2 -> right);
}else if(t1 == NULL && t2 != NULL){
root = new TreeNode(t2 -> val);
root -> left = mergeTrees(t1, t2 -> left);
root -> right = mergeTrees(t1, t2 -> right);
}else if(t1 != NULL && t2 == NULL){
root = new TreeNode(t1 -> val);
root -> left = mergeTrees(t1 -> left, t2);
root -> right = mergeTrees(t1 -> right, t2);
}
return root;
}
};
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
if(t1 == NULL && t2 == NULL){
return NULL;
}
if(t1 == NULL){
return t2;
}
if(t2 == NULL){
return t1;
}
TreeNode* newNode = new TreeNode(t1 -> val + t2 -> val);
newNode -> left = mergeTrees(t1 -> left, t2 -> left);
newNode -> right = mergeTrees(t1 -> right, t2 -> right);
return newNode;
}
};
20200203递归版本解题思路
- 首先，这个最后的结果不是在原来的基础上返回的
- 需要重新分配节点指针，然后初始化
- 思路基本上是正确的，就是有些犹豫最后的结果
