二叉树的创建和后序序列化

二叉树的创建：

二叉树的创建有两种方式：递归和非递归。

递归方式：

递归方式是最常用的二叉树创建方式。递归创建二叉树的过程是：先创建根节点，然后递归创建左子树和右子树。具体步骤如下：

1. 创建一个根节点；

2. 如果输入序列为空，则返回空树；

3. 否则，将序列的第一个元素作为根节点的值；

4. 将输入序列分成左子树序列和右子树序列，左子树序列包含根节点的左子树，右子树序列包含根节点的右子树；

5. 递归创建左子树和右子树。

递归方式的实现代码如下：

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def create_tree(preorder):
    if not preorder:
        return None
    
    root_val = preorder.pop(0)
    root = Node(root_val)
    
    left_preorder = []
    right_preorder = []
    for val in preorder:
        if val < root_val:
            left_preorder.append(val)
        else:
            right_preorder.append(val)
    
    root.left = create_tree(left_preorder)
    root.right = create_tree(right_preorder)
    
    return root

非递归方式：

非递归方式是通过使用栈来实现的。具体步骤如下：

1. 创建一个空栈和一个根节点；

2. 将根节点入栈；

3. 从输入序列中取出下一个元素，如果该元素小于栈顶节点的值，说明该元素是栈顶节点的左子节点，将该元素作为左子节点入栈；

4. 如果该元素大于栈顶节点的值，说明该元素是栈顶节点的右子节点，将该元素作为右子节点入栈；

5. 重复步骤3和步骤4，直到输入序列为空。

非递归方式的实现代码如下：

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def create_tree(preorder):
    if not preorder:
        return None
    
    root = Node(preorder[0])
    stack = [root]
    
    for val in preorder[1:]:
        node = Node(val)
        if val < stack[-1].val:
            stack[-1].left = node
            stack.append(node)
        else:
            while stack and val > stack[-1].val:
                last = stack.pop()
            last.right = node
            stack.append(node)
    
    return root

二叉树的后序序列化：

二叉树的后序序列化是指将一棵二叉树转化为一个字符串，使得该字符串可以唯一地表示该二叉树。具体步骤如下：

1. 如果根节点为空，则返回空字符串；

2. 递归序列化左子树和右子树；

3. 将根节点的值加入序列化字符串中。

后序序列化的实现代码如下：

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def serialize(root):
    if not root:
        return ""
    
    left = serialize(root.left)
    right = serialize(root.right)
    
    return left + right + str(root.val) + " "