Leetcode Python超琐碎笔记: 617. Merge Two Binary Trees

问题地址，难度：Easy

若有错误之处请予以指正:)

问题描述

Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.

You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.

Example 1:

Input: 
    Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  

Output: 
Merged tree:
         3
        / \
       4   5
      / \   \ 
     5   4   7

Note: The merging process must start from the root nodes of both trees.

题意分析

这道题属于一想通就能一下做出来的。首先merge树的子问题是merge节点/子树，从根节点开始，返回的结果应作为当前节点的左右子树；其次merged tree的结构包含了原始两个树的结构，所以可以在任选一个原始树进行in-place的merge，有的留下或者更新值，没有的补上（当这棵树上没有一个节点/子树时，把另一棵上对应的节点/子树接上来）。

树结构上的递归真是无处不在（比如Parser），一旦想清楚，实现出来往往令人觉得优雅而有趣。贴一个做这道题前没多久做的Golang练习，也是两个树之间的问题：判断二叉查找树是否等价。

我的实现及调优过程

方法1：100 ms

暂时没有想到除此以外更好的方法。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def mergeTrees(self, t1, t2):
        """
        :type t1: TreeNode
        :type t2: TreeNode
        :rtype: TreeNode
        """
        return merge(t1, t2)
        
def merge(t1, t2):    
    if t1 is None:
        return t2
    elif t2 is None:
        return t1
    else:
        t1.val = t1.val + t2.val
        t1.left = merge(t1.left, t2.left)
        t1.right = merge(t1.right, t2.right)
        return t1

• 时间复杂度：O(n) （n为merged tree的节点数）
• 空间复杂度：O(1) （未创建新变量，但实际上递归本身的栈会占用一些资源）