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

二叉树的遍历主要有三种：先序遍历（根节点 -> 左子树 -> 右子树）、中序遍历（左子树 -> 根节点 -> 右子树）和后序遍历（左子树 -> 右子树 -> 根节点）。这里我会分别介绍递归和非递归实现这两种遍历方式。

**1. 递归算法：**

### 先序遍历（递归）

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void preorderTraversal(TreeNode* root) {
    if (root != nullptr) {
        // 访问当前节点
        cout << root->val << " ";
        // 递归遍历左子树
        preorderTraversal(root->left);
        // 递归遍历右子树
        preorderTraversal(root->right);
    }
}

### 中序遍历（递归）

void inorderTraversal(TreeNode* root) {
    if (root != nullptr) {
        // 递归遍历左子树
        inorderTraversal(root->left);
        // 访问当前节点
        cout << root->val << " ";
        // 递归遍历右子树
        inorderTraversal(root->right);
    }
}

### 后序遍历（递归）

void postorderTraversal(TreeNode* root) {
    if (root != nullptr) {
        // 递归遍历左子树
        postorderTraversal(root->left);
        // 递归遍历右子树
        postorderTraversal(root->right);
        // 访问当前节点
        cout << root->val << " ";
    }
}

**2. 非递归算法（使用栈）：**

### 先序遍历（非递归）

void preorderTraversalNonRecursive(TreeNode* root, stack<TreeNode*> &st) {
    while (root || !st.empty()) {
        while (root) {
            cout << root->val << " ";
            st.push(root);
            root = root->left;
        }
        root = st.top();
        st.pop();
        root = root->right;
    }
}

### 中序遍历（非递归）

void inorderTraversalNonRecursive(TreeNode* root, stack<TreeNode*> &st) {
    stack<TreeNode*> tempStack;
    TreeNode* current = root;

    while (current || !st.empty() || !tempStack.empty()) {
        while (current) {
            tempStack.push(current);
            current = current->left;
        }
        current = tempStack.top();
        tempStack.pop();
        cout << current->val << " ";
        current = current->right;
    }
}

### 后序遍历（非递归）

void postorderTraversalNonRecursive(TreeNode* root, stack<TreeNode*> &st) {
    stack<TreeNode*> firstStack, secondStack;
    firstStack.push(root);

    while (!firstStack.empty()) {
        TreeNode* node = firstStack.top();
        firstStack.pop();

        secondStack.push(node);

        if (node->left) {
            firstStack.push(node->left);
        }
        if (node->right) {
            firstStack.push(node->right);
        }
    }

    while (!secondStack.empty()) {
        cout << secondStack.top()->val << " ";
        secondStack.pop();
    }
}