题解 | 合并二叉树

1、解题思路

1. 递归方法：从两棵树的根节点开始递归合并。如果两个节点都存在，创建一个新节点，值为两节点值之和。递归合并左子树和右子树。如果其中一个节点为空，直接返回另一个节点。
2. 迭代方法（BFS或DFS）：使用队列或栈同时遍历两棵树。每次取出两个树的对应节点，按照规则合并。将合并后的节点的子节点加入队列或栈继续处理。

2、代码实现

C++（递归）

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

        TreeNode* merged = new TreeNode(t1->val + t2->val);
        merged->left = mergeTrees(t1->left, t2->left);
        merged->right = mergeTrees(t1->right, t2->right);

        return merged;
    }
};

C++（迭代）

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

        queue<TreeNode*> q;
        q.push(t1);
        q.push(t2);

        while (!q.empty()) {
            TreeNode* node1 = q.front();
            q.pop();
            TreeNode* node2 = q.front();
            q.pop();

            node1->val += node2->val;

            if (node1->left && node2->left) {
                q.push(node1->left);
                q.push(node2->left);
            } else if (node2->left) {
                node1->left = node2->left;
            }

            if (node1->right && node2->right) {
                q.push(node1->right);
                q.push(node2->right);
            } else if (node2->right) {
                node1->right = node2->right;
            }
        }

        return t1;
    }
};

Java（递归）

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 merged = new TreeNode(t1.val + t2.val);
        merged.left = mergeTrees(t1.left, t2.left);
        merged.right = mergeTrees(t1.right, t2.right);
        
        return merged;
    }
}

Java（迭代）

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;
        
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(t1);
        q.offer(t2);
        
        while (!q.isEmpty()) {
            TreeNode node1 = q.poll();
            TreeNode node2 = q.poll();
            
            node1.val += node2.val;
            
            if (node1.left != null && node2.left != null) {
                q.offer(node1.left);
                q.offer(node2.left);
            } else if (node2.left != null) {
                node1.left = node2.left;
            }
            
            if (node1.right != null && node2.right != null) {
                q.offer(node1.right);
                q.offer(node2.right);
            } else if (node2.right != null) {
                node1.right = node2.right;
            }
        }
        
        return t1;
    }
}

Python（递归）

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param t1 TreeNode类 
# @param t2 TreeNode类 
# @return TreeNode类
#
class Solution:
    def mergeTrees(self , t1: TreeNode, t2: TreeNode) -> TreeNode:
        # write code here
        if not t1:
            return t2
        if not t2:
            return t1
        
        merged = TreeNode(t1.val + t2.val)
        merged.left = self.mergeTrees(t1.left, t2.left)
        merged.right = self.mergeTrees(t1.right, t2.right)
        
        return merged

Python（迭代）

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param t1 TreeNode类 
# @param t2 TreeNode类 
# @return TreeNode类
#
from collections import deque

class Solution:
    def mergeTrees(self , t1: TreeNode, t2: TreeNode) -> TreeNode:
        # write code here
        if not t1:
            return t2
        if not t2:
            return t1
        
        q = deque()
        q.append(t1)
        q.append(t2)
        
        while q:
            node1 = q.popleft()
            node2 = q.popleft()
            
            node1.val += node2.val
            
            if node1.left and node2.left:
                q.append(node1.left)
                q.append(node2.left)
            elif node2.left:
                node1.left = node2.left
            
            if node1.right and node2.right:
                q.append(node1.right)
                q.append(node2.right)
            elif node2.right:
                node1.right = node2.right
        
        return t1

3、复杂度分析

• 时间复杂度：O(n)，每个节点被访问一次。
• 空间复杂度：递归方法为 O(h)（树高），迭代方法为 O(n)（队列存储节点）。