617. Merge Two Binary Trees ¶ Time: $O(n)$ Space: $O(\log n)$ C++JavaPython 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15class 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 11class 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 11class 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