undefined

前序、中序、后序的非递归算法

前序

void PreOrderIteration(TreeNode* root) {
    if (root == nullptr) return;
    std::stack<TreeNode*> st;
    st.push(root);
    while (!st.empty()) {
        auto node = st.top();
        std::cout << node->value << ' ';
        st.pop();
        if (node->right != nullptr) {
            st.push(node->right);
        } 
        if (node->left != nullptr) {
            st.push(node->left);
        }
    }
}

中序

void InOrder(Node* root) {
    if (root == nullptr) return;
    std::stack<Node*> st;
    while (!st.empty() || root != nullptr) {
        while (root != nullptr) {
            st.push(root);
            root = root->left;
        }
        root = st.top();
        std::cout << root->value << " ";
        st.pop();
        root = root->right;
    }
}

后序

void PostOrderIteration(TreeNode* root) {
    if (root == nullptr) return;
    std::stack<TreeNode*> st1;
    std::stack<int> st2;
    st1.push(root);
    while (!st1.empty()) {
        TreeNode* node = st1.top();
        st2.push(node->value);
        st1.pop();
        if (node->left != nullptr) {
            st1.push(node->left);
        }
        if (node->right != nullptr) {
            st1.push(node->right);
        }
    }
    while (!st2.empty()) {
        std::cout << st2.top() << ' ';
        st2.pop();
    }
    std::cout << std::endl;
}

void PostOrderIteration2(TreeNode* root) {
    if (root == nullptr) return;
    TreeNode* cur = root;
    std::stack<TreeNode*> st;
    st.push(root);
    while (!st.empty()) {
        TreeNode* node = st.top();
        if (node->left != nullptr && node->left != cur && node->right != cur) {
            st.push(node->left);
        } else if (node->right != nullptr && node->right != cur) {
            st.push(node->right);
        } else {
            std::cout << st.top()->value << ' ';
            st.pop();
            cur = node;
        }
    }
}

// 非递归 后续遍历
// 第二种方法：一个栈
// 与中序遍历不同的是：
// 1. 中序遍历（左根右）中，从栈中弹出的节点，其左子树是访问完了，接下来就可以访问这个节点，然后在访问右子树
// 2. 后序遍历（左右根）中，从栈中弹出的节点，可以确认其左子树访问完了，但是右子树无法确认是否访问过
// 因此，在后序遍历中，引入一个 prev 来记录历史访问记录
// 1. 当访问完一颗子树时，我们就用 prev 指向该节点
// 2. 这样，在回溯到父节点的时候，我们可以依据 prev 是指向左子节点还是右子节点，来判断父节点的访问情况
void PostOrder2(Node* root) {
    if (root == nullptr) return;
    std::stack<Node*> st;
    Node* prev = nullptr;
    // 主要思想：
    // 由于在某棵子树访问完成之后，接着就要回溯到其父节点去
    // 因此可以用 prev 来记录访问历史，在回溯到父节点时，可以由此来判断，上一个访问的节点是否为右子树
    while (root != nullptr || !st.empty()) {
        while (root != nullptr) {
            st.push(root);
            root = root->left;
        }
        // 从栈中拿出元素，此时可以确认此节点的左子树一定访问完了，但是右子树不一定访问了，所以不能弹出
        root = st.top();
        // 如果此节点的右子树为空或者右子树已经访问过，则可以访问此节点了
        if (root->right == nullptr || root->right == prev) {
            // 访问并弹出
            std::cout << root->value << " ";
            st.pop();
            // 并把这个节点用 prev 保存起来，为了确认此节点所代表的子树时左子树还是右子树
            //更新历史访问记录，这样回溯的时候父节点可以由此判断右子树是否访问完成
            prev = root;
            // 将 root 置空，因为 root 节点已经被访问，并且确认此节点左右子树也被访问，就让此节点消失
            root = nullptr;
        } else {
            // 如果右子树没有被访问，那么访问右子树
            root = root->right;
        }
    }
}

层序遍历

// 层序遍历
void LevelOrder(Node* root) {
    if (root == nullptr) return;
    std::queue<Node*> qu;
    qu.push(root);
    while (!qu.empty()) {
        int cur_level_size = qu.size();
        for (int i = 0; i < cur_level_size; i++) {
            Node* tmp = qu.front();
            std::cout << tmp->value << " ";
            qu.pop();
            if (tmp->left != nullptr) {
                qu.push(tmp->left);
            }
            if (tmp->right != nullptr) {
                qu.push(tmp->right);
            }
        }
        std::cout << std::endl;
    }
}