## Merge Two Binary Trees

• Time:O(n)
• Space:O(\log n)

## C++

``````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;
}
};
``````

## JAVA

``````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;
}
}
``````

## Python

``````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
``````