二叉树的合并[C]

给定两个根结点root1和root2，二叉树的合并目的是将两个树合成一个数，合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。（题目来源于leetcode）

例子如下图： 

输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]

输出：[3,4,5,5,4,null,7]

树的结点定义如下：

struct TreeNode {

      int val;

      struct TreeNode *left;

      struct TreeNode *right;

  };

很明显，合并可以通过递归来实现，C语言代码如下：

struct TreeNode* mergeTrees(struct TreeNode* root1, struct TreeNode* root2){
    if(root1 == NULL)  return root2;   //树一定要先判断是否为空，这里为空的同时也是返回的条件
    if(root2 == NULL)  return root1;
    struct TreeNode* res = malloc(sizeof(struct TreeNode));  //创建结点，一定要申请空间
    res->val = root1->val + root2->val;
    res->left = mergeTrees(root1->left, root2->left);   //左结点递归即可
    res->right = mergeTrees(root1->right, root2->right);
    return res;  //返回创建的新树的根结点
}

 让我们来分析一下时间复杂度和空间复杂度，不妨令两棵原树的结点数是a和b，则很明显，时间复杂度是O(min(a,b))，空间复杂度取决于递归的栈深度，也是O(min(a,b))，这是因为递归的层数不会超过结点少的那棵树的结点树，当那棵树为一条链时会有最坏情况。