LeetCode合并二叉树代码样例通过但提交报错问题求助

问题根因 #

代码的核心bug出现在单侧节点为空的分支逻辑里：当node1或node2其中一个为null时，仅给新节点赋值了当前val，没有递归遍历对应非空节点的左右子树，导致非空节点的子树全部丢失，这就是提交测试用例报错的原因。
比如测试用例中出现root1为null、root2还有多层子节点的场景，原有代码只会返回根节点带val，左右子节点全为null的错误结果。

修正后的代码 #

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        return traverse(root1, root2);
    }

    public TreeNode traverse(TreeNode node1, TreeNode node2){
        if(node1 == null && node2 == null){
            return null;
        }
        TreeNode newNode = new TreeNode();
        if(node1 == null){
            newNode.val = node2.val;
            newNode.left = traverse(null, node2.left);
            newNode.right = traverse(null, node2.right);
        } else if(node2 == null){
            newNode.val = node1.val;
            newNode.left = traverse(node1.left, null);
            newNode.right = traverse(node1.right, null);
        } else {
            newNode.val = node1.val + node2.val;
            newNode.left = traverse(node1.left, node2.left);
            newNode.right = traverse(node1.right, node2.right);
        }
        return newNode;
    }
}

代码优化建议 #

• 可以省略不必要的中间变量，比如mergeTrees方法里直接返回traverse的结果即可，不需要额外定义ret变量
• 如果题目允许修改原二叉树的结构，还可以不需要新建节点，直接在非空的原节点上修改值拼接子树，大幅减少内存消耗：

// 优化版（修改原树，无需额外新建全部节点）
class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1 == null) return root2;
        if(root2 == null) return root1;
        root1.val += root2.val;
        root1.left = mergeTrees(root1.left, root2.left);
        root1.right = mergeTrees(root1.right, root2.right);
        return root1;
    }
}

内容的提问来源于stack exchange，提问作者Matt Angelucci