Skip to content

617. Merge Two Binary Trees 👍

  • Time: $O(n)$
  • Space: $O(\log n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
 public:
  TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
    if (root1 == nullptr && root2 == nullptr)
      return nullptr;
    const int val = (root1 == nullptr ? 0 : root1->val) +
                    (root2 == nullptr ? 0 : root2->val);
    TreeNode* root = new TreeNode(val);
    root->left = mergeTrees(root1 == nullptr ? nullptr : root1->left,
                            root2 == nullptr ? nullptr : root2->left);
    root->right = mergeTrees(root1 == nullptr ? nullptr : root1->right,
                             root2 == nullptr ? nullptr : root2->right);
    return root;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
  public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
    if (root1 == null && root2 == null)
      return null;
    final int val = (root1 == null ? 0 : root1.val) + (root2 == null ? 0 : root2.val);
    TreeNode root = new TreeNode(val);
    root.left = mergeTrees(root1 == null ? null : root1.left, root2 == null ? null : root2.left);
    root.right = mergeTrees(root1 == null ? null : root1.right, root2 == null ? null : root2.right);
    return root;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
  def mergeTrees(
      self,
      root1: TreeNode | None,
      root2: TreeNode | None,
  ) -> TreeNode | None:
    if not root1 and not root2:
      return None
    val = (root1.val if root1 else 0) + (root2.val if root2 else 0)
    root = TreeNode(val)
    root.left = self.mergeTrees(root1.left if root1 else None,
                                root2.left if root2 else None)
    root.right = self.mergeTrees(root1.right if root1 else None,
                                 root2.right if root2 else None)
    return root