LeetCode 617. 合并二叉树

Categories:

题目描述
思路分析
1. 解法一：递归合并（推荐）
相似题目

题目描述

✅ 617. 合并二叉树

思路分析

解法一：递归合并（推荐）

核心思路：

两棵树对应结点同时存在时相加，只有一棵存在时直接复用。

递归处理左右子树即可完成合并。

这是典型的树结构同步遍历。

复杂度分析：

时间复杂度：O(n)，其中 n 为较大树的结点数。

空间复杂度：O(h)，递归栈深度为树高。

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null) {
            return root2;
        }
        if (root2 == null) {
            return root1;
        }

        // 同步递归合并左右子树
        TreeNode root = new TreeNode(root1.val + root2.val);
        root.left = mergeTrees(root1.left, root2.left);
        root.right = mergeTrees(root1.right, root2.right);
        return root;
    }
}

func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
    if root1 == nil {
        return root2
    }
    if root2 == nil {
        return root1
    }

    // 同步递归合并左右子树
    root := &TreeNode{Val: root1.Val + root2.Val}
    root.Left = mergeTrees(root1.Left, root2.Left)
    root.Right = mergeTrees(root1.Right, root2.Right)
    return root
}

相似题目

题目	难度	考察点
226. 翻转二叉树	简单	递归
100. 相同的树	简单	递归
101. 对称二叉树	简单	递归
104. 二叉树的最大深度	简单	递归
111. 二叉树的最小深度	简单	递归

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/38409747