题解 | #合并二叉树#

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param t1 TreeNode类 
 * @param t2 TreeNode类 
 * @return TreeNode类
 */
struct TreeNode* mergeTrees(struct TreeNode* t1, struct TreeNode* t2 )
{
    // 递归解法
    // 对于任意同一位置的节点——由调用时，传递入 mergeTrees的节点保证
    // 1.如果两个都为NULL，直接退出，返回第一颗即可，都一样
    // 2.有且仅有一个为NULL，此时，直接返回非空的一棵树即可；
    // 3.两颗都非NULL，相加，同时，进一步递归 该节点的左右子树；

    if( (NULL == t1) && (NULL == t2) )
        return NULL;

    if(NULL != t1)
    {
        if(NULL == t2)
            return t1;

        // 另一可能是 t1 && t2  
    } 

    if(NULL != t2)
    {
        if(NULL == t1)
            return t2;

        // 另一可能是 t1 && t2
    }

    // t1 && t2
    t1->val += t2->val;
    // 递归调用 但如何处理这个返回值，调用也没问题，因为t1本身不会被改变？？？小心语法细节，没问题，你只是处理了t1的东西，t1本身不会变
    t1->left = mergeTrees(t1->left,t2->left);
    t1->right = mergeTrees(t1->right,t2->right);
    return t1;
 
}

前面大概花了30分钟，没思路。

看了答案后，确认用递归尝试，到完成，大概30分钟。

只是构建测试的时候多花了些时间。

保留了原始的备注，没加以修改。

这是刷的第一题。

有两个点，觉得可以改善更好：

1、自己写的测试用例，如果牛客网也能运行出一个期望结果就好了；

2、对于这个题目里，输入和输出——数组表示的二叉树方式（可能这是基础内容，我很久没看二叉树了，以前看的也忘了）

所以，一开始，我对于什么地方要填#是有点疑虑的。

——后面看书了，再来这里补充。

这个题目，因为要求空间复杂度是 O(1),所以一开始就直觉觉得是递归题。

但因为不够熟练（递归 和 二叉树，前者缺乏深刻认识，后者对它的操作不是很熟悉）

所以没有马上采用这个思路往下想。

后来思考了约30分钟，实在没思路，就看了一下别人的答案。

其实并没很认真看，因为不需要——看一眼就意识到对方果然是用递归在做，而且，没想到这个操作所需的代码这么少，于是，就直接往递归的思路上自己思考。

思考中，最大的障碍，出在一个地方——因为需要一层一层往下走，我总是担心递归“会让我不知道自己在哪一层”

后来画图，慢慢思考，发现，这是一个根本不需要担心的事情。

因为，每一次，它都针对同一个位置的节点操作，然后返回这个节点。至于在这个节点的函数里执行对它的左右子节点的操作，并不会影响到父节点。

至此，思路打开。

剩下的，对于递归，最重要的就是，确认它的终止条件，确保一定可以遍历到头就可以了。

这个就是对 t1 t2 是NULL非NULL的分类。

我印象里有些答案写得很精彩，用 while条件解决。

但我没想到，我还是用本质上形如 switch-case 的方式，分了四种情形——写了四个if的方式。

其实我并没有在这个思路完成后，去思考一下 时间 和 空间度是否满足要求。

但是，现在反过来想想，是可以的。

空间上：

因为根本就没有使用任何形参以外的变量，所以，空间是一个和递归次数（层数，N）无关的复杂度，自然就是常数空间复杂度；

时间上：

因为需要遍历二叉树，递归某种程度上和循环，其实是类似的。显然都是N的函数。

但是，整个函数的实现，不存在进一步使用循环（其实这里我有个地方不太懂，就是对于计算递归，不断往下递归，这个应该怎么算复杂度？）

如上，这个复杂度其实不会算，待学习。