leetcode 617. Merge Two Binary Trees | 617. 合并二叉树（Java）

￡神魔★判官ぃ 2022-10-17 13:49 132阅读 0赞

## 题目 ##

[https://leetcode-cn.com/problems/merge-two-binary-trees/][https_leetcode-cn.com_problems_merge-two-binary-trees]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

##### 测试用例 #####

> 输入：  
> \[1,3,2,5\]  
> \[2,1,3,null,4,null,7\]  
> \[1\]  
> \[1,2\]  
> \[1,null,2,null,3,null,4\]  
> \[1,2,null,3,null,4,null,5\]  
> 答案：  
> \[3,4,5,5,4,null,7\]  
> \[2,2\]  
> \[2,2,2,3,null,null,3,4,null,null,4,5\]

##### 思路 #####

同时遍历左右两棵二叉树，把右边的树上的值加到左边来。

这样做有一个不严谨的地方，是改变了原有二叉树的值，而题目中要求返回一个 new tree。

public static TreeNode mergeTrees(TreeNode root1, TreeNode root2) { 
        if (root1 != null && root2 != null) { 
            root1.val = root1.val + root2.val; // already ensure both nodes are not null
            if (root1.left != null && root2.left != null)
                mergeTrees(root1.left, root2.left);
            if (root1.right != null && root2.right != null)
                mergeTrees(root1.right, root2.right);
            if (root1.left == null)
                root1.left = root2.left;
            if (root1.right == null)
                root1.right = root2.right;
        } else if (root1 == null) { 
            root1 = root2;
        }
        return root1;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

[https_leetcode-cn.com_problems_merge-two-binary-trees]: https://leetcode-cn.com/problems/merge-two-binary-trees/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20221014/dee3cee56ee841fdb4d613f388e968ac.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20221014/14c8267853fd4536bbde13d15ecd2945.png