题解 | #合并二叉树#

方法：递归

将问题分解为，合并当前结点和合并当前结点的两个二叉树两个部分。可以运用递归进行合并。

时间复杂度：o(min(n,m))，m和n分别为两棵树的节点树，当一个树访问完时，自然就连接上另一个树的节点，故只访问了小树的节点数。

空间复杂度：o(min(n,m))，递归栈深度也同时间，只访问了小树的节点数。

class Solution {
  public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
	  	//如果其中一个树的结点不存在，合并后的树节点即为另一个树的结点
        if (t1 == nullptr)
            return t2;
        if (t2 == nullptr)
            return t1;
		//两个结点都存在，将值合并
        TreeNode* t = new TreeNode(t1->val + t2->val);
        t->left = mergeTrees(t1->left, t2->left);
        t->right = mergeTrees(t1->right, t2->right);

        return t;
    }
};