题目链接:
144. 二叉树的前序遍历 - 力扣（LeetCode）
94. 二叉树的中序遍历 - 力扣（LeetCode）
145. 二叉树的后序遍历 - 力扣（LeetCode）

普通迭代

由于后序遍历可通过左右颠倒的前序反转后得到，所以我们只用完成前序和中序两种。

(1)前序
思路：
指针从根节点开始：中节点加入数组，右节点入栈，指针移至左节点
重复上述过程直至结束(栈空+指针指空)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> preorderTraversal(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> st;
    TreeNode* p = root;
    while (p != nullptr || !st.empty()) {
        if (p == nullptr) {
            p = st.top();
            st.pop();
        } else {
            res.emplace_back(p->val);
            st.push(p->right);
            p = p->left;
        }
    }
    return res;
}

(2)中序
思路：
指针从根节点开始：若指针非空，则节点入栈，指针移至左节点；若指针指空，读取栈顶，加入数组，指针移至右节点。循环结束同上

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> inorderTraversal(TreeNode* root) {
    vector<int> res;
    TreeNode* p = root;
    stack<TreeNode*> st;
    while (p != nullptr || !st.empty()) {
        if (p == nullptr) {
            p = st.top();
            res.emplace_back(p->val);
            st.pop();
            p = p->right;
        } else {
            st.push(p);
            p = p->left;
        }
    }
    return res;
}

标记迭代

有两种方法：空指针标记和boolean标记
思路是一样的：通过标记判断节点是第一次被读到还是再取栈时被读到
下面都用后序举例

(1)空指针标记
在第一次读到的节点入栈后再将一个空指针入栈以作标记

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<int> postorderTraversal(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> st;
    TreeNode *p;
    if (root != nullptr) st.push(root);
    while (!st.empty()) {
        p = st.top();
        st.pop();
        if (p == nullptr) {
            p = st.top();
            st.pop();
            res.emplace_back(p->val);
        } else {
            st.push(p);
            st.push(nullptr);
            if (p->right) st.push(p->right); //避免加入空指针
            if (p->left) st.push(p->left);
        }
	}
    return res;
}

(2)boolean标记
主要是学习语法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<int> postorderTraversal(TreeNode* root) {
    vector<int> res;
    stack<pair<TreeNode*, bool>> st;
    if (root != nullptr) st.push(make_pair(root, false));
    while (!st.empty()) {
        auto p = st.top().first;
        auto visited = st.top().second;
        st.pop();
        if (visited) {
            res.emplace_back(p->val);
        } else {
            st.push(make_pair(p, true));
            if (p->right) st.push(make_pair(p->right, false));
            if (p->left) st.push(make_pair(p->left, false));
        }
    }
    return res;
}

标记迭代中的前序中序只需将后序中构造的三行换位置即可，思路高度统一

(3)Morris遍历
Morris中序遍历