掌握建立二叉树的方法，实现先序、中序、后序三种遍历的递归算法和非递归算法。

在计算机科学中，二叉树是一种常见的数据结构，由节点组成，每个节点最多有两个子节点，通常称为左子节点和右子节点。建立二叉树的基本方法通常是通过递归：

1. **构造函数+递归**：
- 对于根节点，创建一个新的节点并将其设置为根；
- 对于左子节点，如果给定值存在，则递归地在左子树中插入；
- 对于右子节点，同理在右子树中插入。

先序、中序和后序遍历是访问二叉树节点的一种顺序：
- **先序遍历**（根-左-右）：先访问根节点，然后递归地遍历左子树，最后遍历右子树。
- **中序遍历**（左-根-右）：先递归地遍历左子树，然后访问根节点，最后遍历右子树。
- **后序遍历**（左-右-根）：先递归地遍历左子树和右子树，最后访问根节点。

以下是这三种遍历的递归和非递归算法：

### 递归算法

# 先序遍历（递归）
def preorder_traversal(root):
    if root is not None:
        print(root.val)
        preorder_traversal(root.left)
        preorder_traversal(root.right)

# 中序遍历（递归）
def inorder_traversal(root):
    if root is not None:
        inorder_traversal(root.left)
        print(root.val)
        inorder_traversal(root.right)

# 后序遍历（递归）
def postorder_traversal(root):
    if root is not None:
        postorder_traversal(root.left)
        postorder_traversal(root.right)
        print(root.val)

### 非递归算法（利用栈实现）

# 先序遍历（非递归）
def preorder_iterative(root):
    stack = [root]
    while stack:
        node = stack.pop()
        if node is not None:
            print(node.val)
            stack.append(node.right)
            stack.append(node.left)

# 中序遍历（非递归）
def inorder_iterative(root):
    stack, current = [], root
    while stack or current:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        print(current.val)
        current = current.right

# 后序遍历（非递归）
def postorder_iterative(root):
    def backtrack(node, prev):
        if node is not None:
            backtrack(node.left, node)
            backtrack(node.right, node)
            if prev is None or node != prev.left and node != prev.right:
                result.append(node.val)
    result = []
    backtrack(root, None)
    print(result[::-1])