建立二叉树用非递归判断栈空的方法实现先序,中序,后序遍历

二叉树的非递归遍历通常使用栈来实现，其中，先序、中序和后序遍历的实现方法各不相同。下面分别介绍一下这三种遍历的非递归实现方法。

先序遍历：
1. 将根节点入栈；
2. 取出栈顶节点，访问它，然后依次将其右孩子、左孩子入栈；
3. 重复步骤2，直到栈为空。

C++代码实现：

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> st;
    if (root != nullptr) st.push(root);
    while (!st.empty()) {
        TreeNode* node = st.top(); st.pop();
        res.push_back(node->val);
        if (node->right != nullptr) st.push(node->right);
        if (node->left != nullptr) st.push(node->left);
    }
    return res;
}

中序遍历：
1. 将根节点入栈；
2. 持续将左孩子入栈，直到左孩子为空；
3. 取出栈顶节点，访问它，然后将其右孩子入栈；
4. 重复步骤2和3，直到栈为空。

C++代码实现：

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> st;
    TreeNode* node = root;
    while (node != nullptr || !st.empty()) {
        while (node != nullptr) {
            st.push(node);
            node = node->left;
        }
        node = st.top(); st.pop();
        res.push_back(node->val);
        node = node->right;
    }
    return res;
}

后序遍历：
1. 将根节点入栈；
2. 持续将左孩子入栈，直到左孩子为空；
3. 如果栈顶节点的右孩子为空或者已经访问过了，就取出该节点并访问它，否则将其右孩子入栈；
4. 重复步骤2和3，直到栈为空。

C++代码实现：

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> st;
    TreeNode* last = nullptr;
    while (root != nullptr || !st.empty()) {
        while (root != nullptr) {
            st.push(root);
            root = root->left;
        }
        TreeNode* node = st.top();
        if (node->right == nullptr || node->right == last) {
            res.push_back(node->val);
            last = node;
            st.pop();
        } else {
            root = node->right;
        }
    }
    return res;
}

以上是二叉树先序、中序、后序遍历的非递归实现方法，利用栈的特点，可以很好地模拟递归过程。