合并,就是两个树的结构交集部分,数据相加,否则,取非空部分。
所以,这里相当于是对两棵树同时遍历: 如果两棵树节点都不为空,则数据相加, 否则,直接指针把不为空的节点复制过来。注:这里没有申请内存,而直接对原有的树进行改造,这样可以节省申请内存的时间,且节省一些内存。
struct TreeNode* mergeTrees(struct TreeNode* t1, struct TreeNode* t2){ struct TreeNode *pTemp = NULL; if ((NULL == t1) && (NULL == t2)) return NULL; else if ((NULL != t1) && (NULL != t2)) { pTemp = t1; pTemp->val = t1->val + t2->val; } else if (NULL != t1) { return t1; } else if (NULL != t2) { return t2; } pTemp->left = mergeTrees(t1->left, t2->left); pTemp->right = mergeTrees(t1->right, t2->right); return pTemp;