【二叉树】合并二叉树

本文介绍: 题目给定两个二叉树想象当你将它们中的一个覆盖到另一个上时两个二叉树的一些节点便会重叠你需要将他们合并为一个新的二叉树合并的规则是如果两个节点重叠那么将他们的值相加作为节点合并后的新值否则不为 NULL 的节点将直接作为新二叉树的节点

0x00 题目

给定两个二叉树
想象当你将它们中的一个 覆盖 到另一个上时
两个二叉树的一些节点便会重叠

你需要将他们合并为一个新的二叉树
合并的规则是如果两个节点重叠
那么将他们的 值相加 作为节点合并后的新值
否则不为 NULL 的节点将直接作为 新 二叉树的节点

0x01 思路

根据合并规则：
两个节点都不为空时，值相加 作为节点新值
有一个为空时，直接使用 非空 的节点
使用递归方式，遍历到每个节点即可

0x02 解法

语言：Swift

树节点：TreeNode

public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init() { self.val = 0; self.left = nil; self.right = nil; }
    public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
    public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
        self.val = val
        self.left = left
        self.right = right
    }
}

解法：

func mergeTrees(_ root1: TreeNode?, _ root2: TreeNode?) -&gt; TreeNode? {
    // 其中一个为空时，返回另一个
    if root1 == nil { return root2 }
    else if root2 == nil { return root1 }
    
    func merge(_ root1: TreeNode?, _ root2: TreeNode?) -&gt; TreeNode? {
        // 其中一个为空时，返回另一个
        if root1 == nil { return root2 }
        else if root2 == nil { return root1 }
    
        // 把节点 root2 覆盖到 root1 上
        root1!.val = root1!.val + root2!.val
        // 依次合并左右节点
        root1!.left = mergeTrees(root1!.left, root2!.left)
        root1!.right = mergeTrees(root1!.right, root2!.right)
        
        return root1!
    }

    return merge(root1, root2)
}