leetcode的第617题--合并二叉树，出现了内存对齐的问题？

Question

我的代码如下：

/*
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.
Input: 
        Tree 1                    Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
Output: 
Merged tree:
         3
        / \
       4   5
      / \   \ 
     5   4   7
*/

/**
 * 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) {
        TreeNode* root;
        TreeNode *t1_left, *t1_right;
        TreeNode *t2_left, *t2_right;

        if (t1 == NULL && t2 == NULL) {
            return NULL;
        }
        else if (t1 != NULL && t2 != NULL) {
            root = new TreeNode(t1->val + t2->val);
            t1_left = t1->left;
            t1_right = t1->right;
            t2_left = t2->left;
            t2_right = t2->right;
        }
        else if (t1 != NULL && t2 == NULL) {
            root = new TreeNode(t1->val);
            t1_left = t1->left;
            t1_right = t1->right;
        }
        else if (t1 == NULL && t2 != NULL) {
            root = new TreeNode(t2->val);
            t2_left = t2->left;
            t2_right = t2->right;
        }

        root->left = mergeTrees(t1_left, t2_left);
        root->right = mergeTrees(t1_right, t2_right);

        return root;
    }
};

出现了内存对齐的问题。我不清楚是我代码写错了还是其他原因？希望前辈可以解答一下。

Answer 1

Runtime Error报的错误是运行时错误(简称RE)，有很多原因，常见的有数组越界，段错误，访问非法内存等等。

---

代码整体思路是对的，条件判断这里有些问题，把这一段代码

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

改为（想想为什么？递归本质是把原问题分为多个小问题）

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

在这里，不能在递归终止时返回空指针，而应该返回递归结束时的地址给上一层。

稍加修改就可以了

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        TreeNode* root;
        TreeNode *t1_left, *t1_right;
        TreeNode *t2_left, *t2_right;

        if (t1 == NULL) {
            return t2;
        }
        if (t2 == NULL) {
            return t1;
        }
        root = new TreeNode(t1->val + t2->val);
        t1_left = t1->left;
        t1_right = t1->right;
        t2_left = t2->left;
        t2_right = t2->right;
        root->left = mergeTrees(t1_left, t2_left);
        root->right = mergeTrees(t1_right, t2_right);

        return root;
    }
};