[PYTHON] Let Code Day12 Starting from Zero "617. Merge Two Binary Trees"

Overview

It seems that coding tests are conducted overseas in interviews with engineers, and in many cases, the main thing is to implement specific functions and classes according to the theme.

As a countermeasure, it seems that a site called Let Code will take measures.

A site that trains algorithmic power that can withstand coding tests that are often done in the home.

I think it's better to have the algorithm power of a human being, so I'll solve the problem irregularly and write down the method I thought at that time as a memo.

Leetcode

Leet Code Table of Contents Starting from Zero

Last time Leet Code Day 11 starting from zero "1315. Sum of Nodes with Even-Valued Grandparent"

Basically, I would like to solve the easy acceptance in descending order.

problem

617. Merge Two Binary Trees

The difficulty level is easy, and there are many good ones.

The problem is to add the numbers for each of the two given binary trees and return a new tree.

As mentioned above, the tree to which the numerical values of each matching part are added is returned as output.

solution

The idea is to return the other node if one of the nodes doesn't exist, add None if both nodes don't exist, and add the numbers if both nodes exist.

This is the one I wrote comprehensively for the time being.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
        if not t1 and not t2:
            return None
        if not t1:
            return t2
        if not t2:
            return t1
        if t1 and t2:
            ans = TreeNode(t1.val + t2.val)
            ans.left = self.mergeTrees(t1.left,t2.left)
            ans.right = self.mergeTrees(t1.right,t2.right)
            return ans
# Runtime: 92 ms, faster than 63.90% of Python3 online submissions for Merge Two Binary Trees.
# Memory Usage: 15.1 MB, less than 5.72% of Python3 online submissions for Merge Two Binary Trees.

Here is a rewrite to try to simplify it a little more

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
        if not t1:
            return t2
        if not t2:
            return t1
        ans = TreeNode(t1.val + t2.val)
        ans.left = self.mergeTrees(t1.left,t2.left)
        ans.right = self.mergeTrees(t1.right,t2.right)
        return ans
        
# Runtime: 84 ms, faster than 94.01% of Python3 online submissions for Merge Two Binary Trees.
# Memory Usage: 14.9 MB, less than 5.72% of Python3 online submissions for Merge Two Binary Trees.

It's faster, albeit uneven.