解题思路

可以不用重新建一个新的树，我们直接在原树上建立即可

一共有一下三种情况

  1. 主有，辅无
  2. 主无，辅有
  3. 主有，辅有

根据这三种情况可以做出以下三种操作(operations)

  1. 直接回溯
  2. 主树连接辅树的下一个节点
  3. 合并两个节点的值

代码

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        def dfs(root1, root2):
            if root1 and root2:
                root1.val += root2.val
            
            if root1.left and root2.left:
                dfs(root1.left, root2.left)
            elif root1.left is None and root2.left:
                root1.left = root2.left
            if root1.right and root2.right:
                dfs(root1.right, root2.right)
            elif root1.right is None and root2.right:
                root1.right = root2.right
        if root1 is None or root2 is None:
            return root2 if root2 else root1
        dfs(root1, root2)
        return root1

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if (root1 == NULL || root2 == NULL) {
            return root1 == NULL ? root2 : root1;
        }
        dfs(root1, root2);
        return root1;
    }
    void dfs(TreeNode* root1, TreeNode* root2) {
        if (root1 && root2) root1->val += root2->val;
        if (root1->left && root2->left) dfs(root1->left, root2->left);
        else if (root1->left == NULL && root2->left) root1->left = root2->left;
        if (root1->right && root2->right) dfs(root1->right, root2->right);
        else if (root1->right == NULL && root2->right) root1->right = root2->right;
    }
};

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
    if root1 == nil{ return root2 }
    if root2 == nil { return root1 }
    dfs(root1, root2)
    return root1
}


func dfs(root1 *TreeNode, root2 *TreeNode) {
    if root1 != nil && root2 != nil { root1.Val += root2.Val }
    if root1.Left != nil && root2.Left != nil { dfs(root1.Left, root2.Left) }
    if root1.Left == nil && root2.Left != nil { root1.Left = root2.Left }
    if root1.Right != nil && root2.Right != nil { dfs(root1.Right, root2.Right) }
    if root1.Right == nil && root2.Right != nil { root1.Right = root2.Right }
}