【剑指offer】序列化二叉树（python）

1. python的嵌套函数，闭包和函数工厂是嵌套函数最重要的用处。如果你看到一个带装饰器的函数，这个装饰器就是一个函数工厂，它以一个函数作为参数，并返回一个新的函数，新的函数使用闭包包括了作为参数的函数。换句话说，装饰器就是一个语法糖，语法糖就是一种便捷写法。

嵌套函数封装了一些函数过程，对于全局命名空间来说，它们是隐藏的。
嵌套函数可以避免自我重复。在大型函数中，可能会重复使用一些代码，比方说，我们写一个处理文件的函数，同时支持文件名或文件对象作为参数：

def process(file_name):
    def do_stuff(file_process):
        for line in file_process:
            print(line)

    if isinstance(file_name, str):
        with open(file_name, 'r') as f:
            do_stuff(f)
    else:
        do_stuff(file_name)

嵌套函数作为闭包和工厂函数。闭包可以使内部函数记住它所在空间的具体状态。准确地说，应该是内部函数制造了闭包。所谓闭包，所“封闭”的是函数帧中的局部变量。

def generate_power(number):
    # 定义内部函数
    def nth_power(power):
        return number ** power
    # 将函数作为外部函数的结果返回
    return nth_power

上述代码，generate_power() 是一个工厂函数，每次调用它时，会返回一个新创建的函数，

"""    Examples of use:
    >>> raise_two = generate_power(2)
    >>> raise_three = generate_power(3)
    >>> print(raise_two(7))# 2的7次方
    128
    >>> print(raise_three(5))# 3的5次方
    243
    """

raise_two、raise_three 指向的是这些新创建的函数；这些新创建的函数，需要一个参数 power，返回的值是 number**power；

那么，这个 number 的值是怎么来的呢？这就是闭包发生作用的地方：nth_power()函数是从外部函数，即工厂函数获取number的值的。整个过程可以分解步骤如下：

调用外部函数：generate_power(2);
创建函数 nth_power()，它需要一个参数 power；
保存 nth_power() 函数帧的状态，其中包括 number=2；
将保存的函数帧状态传递给 generate_power() 函数；
返回 nth_power() 函数；

闭包为 nth_power() 函数提供了初始化数据并将它返回。因此，我们调用这个被返回的函数时，总是可以在其函数帧中找到 number=2。
2. 工厂函数。工厂函数看上去像个函数，其实是类，调用它时实际上生产了该类的一个实例，就像工厂生产货物。
3. 装饰器
以上函数用装饰器写法。装饰器就是一个语法糖，它的基本流程其实和上面所举的 generate_power() 的例子是一致的。

def generate_power(exponent):
    def decorator(f):
        def inner(*args):
            result = f(*args)
            return exponent**result
        return inner
    return decorator

@generate_power
def raise_two(n):
    return n print(raise_two(7))

@generate_power
def raise_three(n):
    return n print(raise_two(5))

解题思路：
树的序列化：先序遍历，“#”表示占位，当前值加下划线‘_’
树的反序列化：利用闭包的特性，加上队列弹出的优点。
时间：19ms，打败91%的代码

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Serialize(self, root):
        # write code here
        if not root:
            return '#'
        re = str(root.val)
        re += '_' + self.Serialize(root.left)
        re += '_' + self.Serialize(root.right)
        return re
    def Deserialize(self, s):
        # 嵌套函数，闭包
        def des(lis):
            if not lis:
                return None
            v = lis.pop(0)
            if v == '#':
                return None
            else:
                head = TreeNode(int(v))
                head.left = des(lis)
                head.right = des(lis)
            return head
        lis = s.split('_')
        return des(lis)

时间：20ms，打败86%的代码
不使用闭包的代码：

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Serialize(self, root):
        # write code here
        if not root:
            return '#'
        res = str(root.val)
        res += ','+self.Serialize(root.left)
        res += ','+self.Serialize(root.right)
        return res
    def Deserialize(self, s):
        lis = s.split(',')
        return self.des(lis)
    def des(self,lis):
            if not lis:
                return None
            v = lis.pop(0)
            if v == '#':
                return None
            else:
                head = TreeNode(int(v))
                head.left = self.des(lis)
                head.right = self.des(lis)
            return head

题解 | #序列化二叉树#

【剑指offer】序列化二叉树（python）