题解 | #合并二叉树#

纠正思路

一开始是想将t2的节点全部都合并到t1，然后递归处理t1和t2的左子树的节点以及t1和t2右子树的节点，最后返回t1的根节点，但是这样处理t1为空t2不为空时，如果将t2的节点赋值给t1，就导致t1后面都有t2的节点了，而且t2节点为空时还会有空指针问题。

正确做法应该是创建一个新的根节点，然后遍历t1和t2的左子树以及t1和t2的右子树，递归地拼接这个根节点的左子树和右子树，最后返回这个新创建的根节点。

参考

参考题解

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param t1 TreeNode类
     * @param t2 TreeNode类
     * @return TreeNode类
     */
    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        // write code here
        if (t1 == null) {
            return t2;
        }
        if (t2 == null) {
            return t1;
        }

        TreeNode ret = new TreeNode(t1.val + t2.val);
        
        ret.left = mergeTrees(t1.left, t2.left);
        ret.right = mergeTrees(t1.right, t2.right);
        return ret;
    }
}

错误思路代码

public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        // write code here
        if (t1 == null && t2 == null) {
            return null;
        }
        if (t1 == null && t2 != null) {
            t1 = t2;  // 不能直接赋值，这样会把t2后面的节点都连给t1了
        }
        if (t1 != null && t2 == null) {
            t2 = t1;
        }
        if (t1 != null && t2 != null) {
            t1.val += t2.val;
        }
        mergeTrees(t1.left, t2.left);
        mergeTrees(t1.right, t2.right);
        return t1;
    }