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
class Solution {
 public:
  TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
    if (!root1 && !root2)
      return nullptr;
    const int val = (root1 ? root1->val : 0) + (root2 ? root2->val : 0);
    TreeNode* root = new TreeNode(val);
    root->left = mergeTrees(root1 ? root1->left : nullptr,
                            root2 ? root2->left : nullptr);
    root->right = mergeTrees(root1 ? root1->right : nullptr,
                             root2 ? root2->right : nullptr);
    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
class Solution:
  def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
    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