617.合并二叉树

链接：617.合并二叉树
难度：Easy
标签：树、深度优先搜索、广度优先搜索、二叉树
简介：给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为  NULL 的节点将直接作为新二叉树的节点。

题解 1 - typescript

• 编辑时间：2020-09-23
• 执行用时：168ms
• 内存消耗：45.5MB
• 编程语言：typescript
• 解法介绍：递归。

function mergeTrees(t1: TreeNode | null, t2: TreeNode | null): TreeNode | null {
  return merge(t1, t2);
  function merge(t1: TreeNode | null, t2: TreeNode | null): TreeNode | null {
    if (t1 === null && t2 === null) return null;
    if (t1 === null) return t2;
    if (t2 === null) return t1;
    const node = new TreeNode(t1.val + t2.val);
    node.left = merge(t1.left, t2.left);
    node.right = merge(t1.right, t2.right);
    return node;
  }
}

题解 2 - cpp

• 编辑时间：2023-08-14
• 执行用时：36ms
• 内存消耗：30.85MB
• 编程语言：cpp
• 解法介绍：递归合并。

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if (!root1 && !root2) return nullptr;
        else if (root1 && !root2) return root1;
        else if (!root1 && root2) return root2;
        else {
            root1->val += root2->val;
            root1->left = mergeTrees(root1->left, root2->left);
            root1->right = mergeTrees(root1->right, root2->right);
            return root1;
        }
    }
};

题解 3 - python

• 编辑时间：2023-08-14
• 执行用时：64ms
• 内存消耗：16.15MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root1 and not root2:
            return None
        elif root1 and not root2:
            return root1
        elif not root1 and root2:
            return root2
        else:
            root1.val += root2.val
            root1.left = self.mergeTrees(root1.left, root2.left)
            root1.right = self.mergeTrees(root1.right, root2.right)
            return root1

题解 4 - rust

• 编辑时间：2023-08-14
• 执行用时：4ms
• 内存消耗：2.3MB
• 编程语言：rust
• 解法介绍：同上。

use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
    pub fn merge_trees(
        root1: Option<Rc<RefCell<TreeNode>>>,
        root2: Option<Rc<RefCell<TreeNode>>>,
    ) -> Option<Rc<RefCell<TreeNode>>> {
        match root1 {
            None => root2,
            Some(mut root1) => match root2 {
                None => Some(root1),
                Some(root2) => {
                    {
                        let mut root1_ref = root1.as_ref().borrow_mut();
                        let mut root2_ref = root2.as_ref().borrow_mut();
                        root1_ref.val += root2_ref.val;
                        {
                            let child1 = root1_ref.left.take();
                            let child2 = root2_ref.left.take();
                            root1_ref.left = Self::merge_trees(child1, child2);
                        }
                        {
                            let child1 = root1_ref.right.take();
                            let child2 = root2_ref.right.take();
                            root1_ref.right = Self::merge_trees(child1, child2);
                        }
                    }
                    Some(root1)
                }
            },
        }
    }
}