Python, Straightforward with Explanation


  • 25

    Let's create a recursive solution.

    • If both trees are empty then we return empty.
    • Otherwise, we will return a tree. The root value will be t1.val + t2.val, except these values are 0 if the tree is empty.
    • The left child will be the merge of t1.left and t2.left, except these trees are empty if the parent is empty.
    • The right child is similar.
    def mergeTrees(self, t1, t2):
        if not t1 and not t2: return None
        ans = TreeNode((t1.val if t1 else 0) + (t2.val if t2 else 0))
        ans.left = self.mergeTrees(t1 and t1.left, t2 and t2.left)
        ans.right = self.mergeTrees(t1 and t1.right, t2 and t2.right)
        return ans
    

  • 0
    T

    I give u a big "LIKE"


  • 0
    Q

    ans.left = self.mergeTrees(t1 and t1.left, t2 and t2.left)

    I'm new to this game, how does "and" work? Could you briefly explain?


  • 17

    @qxlin I am using t1 and t1.left as a shortcut for t1.left if t1 is not None else None.

    Here, "x and y" evaluates as follows: If x is truthy, then the expression evaluates as y. Otherwise, it evaluates as x.

    When t1 is None, then None is falsy, and t1 and t1.left evaluates as t1 which is None.

    When t1 is not None, then t1 is truthy, and t1 and t1.left evaluates as t1.left as desired.

    This is a standard type of idiom similar to the "?" operator in other languages. I want t1.left if t1 exists, otherwise nothing.

    Alternatively, I could use a more formal getattr operator: getattr(t1, 'left', None)


  • 0
    Q

    @awice Thanks so much! I am familiar with '?' operator(or the if else statement), but python always surprises me!


  • 0
    W

    Thanks for nice explaination!


  • 0
    M

    Thanks for sharing a nice looking solution! I tried it and got 132 ms. I was surprised to see that it underperformed my initial naive implementation (125ms). I guess not creating a new TreeNode helps a bit if one of the sides is None:

    def mergeTrees(self, t1, t2):
            """
            :type t1: TreeNode
            :type t2: TreeNode
            :rtype: TreeNode
            """
            if not t1 and not t2:
                return
            
            if not t1:
                res = t2
            elif not t2:
                res = t1
            else:          
                res = TreeNode(t1.val+t2.val)
                res.left = self.mergeTrees(t1.left,t2.left)
                res.right = self.mergeTrees(t1.right,t2.right)
            
            return res
    

  • 0
    A

    Here is a complete analysis of this algorithm:
    http://liqichen.com/daily-leetcode-in-python-merge-two-binary-tree/


  • 0

    Thanks for sharing. I have a revised version of this and I think it is faster and easier to understand:

    def mergeTrees(self, t1, t2):
    
            if t1 and t2:
                root = TreeNode(t1.val + t2.val)
                root.left = self.mergeTrees(t1.left, t2.left)
                root.right = self.mergeTrees(t1.right, t2.right)
                return root
            else:
                return t1 or t2
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.