二叉树前序、中序、后序遍历（非递归统一解法）

Posted on | | Visitors:
Words count in article: 562 字 | Reading time ≈ 3 分

前言

最近复习了二叉树的前序遍历、中序遍历和后序遍历，找到了一种统一的非递归的迭代方法。

思路

思路本质上还是递归，只不过不通过递归函数显式递归，而是通过栈模拟递归。

该思路仅需要微小改动就可以通用于二叉树的先/中/后序遍历，也很容易理解。

注意：

  • 该思路的核心是将nullptr作为可以遍历栈中下1个结点的标志（因此也就不能将空结点压入栈中），即栈中弹出nullptr时就可以遍历下1个栈顶结点，如果不是nullptr则根据遍历顺序入栈，当前根结点入栈时也要将nullptr压入栈中（后续遇到这个nullptr时就可以遍历到该根结点）。
  • 遍历顺序和入栈顺序相反

前序遍历

LeetCode题解：https://www.cnblogs.com/chouxianyu/p/13290758.html

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<int> preorderTraversal(TreeNode* root) {
    vector<int> result;
    stack<TreeNode*> nodes;
    if (root!=nullptr)
        nodes.push(root);
    while(!nodes.empty()){
        root = nodes.top();
        nodes.pop();
        if (root==nullptr){
            result.push_back(nodes.top()->val);
            nodes.pop();
        }else{
            if (root->right!=nullptr)
                nodes.push(root->right);
            if (root->left!=nullptr)
                nodes.push(root->left);
            nodes.push(root);
            nodes.push(nullptr);
        }
    }
    return result;
}

中序遍历

LeetCode题解：https://www.cnblogs.com/chouxianyu/p/13293153.html

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<int> inorderTraversal(TreeNode* root) {
    vector<int> result;
    stack<TreeNode*> nodes;
    if(root!=nullptr)
        nodes.push(root);
    while(!nodes.empty()){
        root=nodes.top();
        nodes.pop();
        if(root==nullptr){
            result.push_back(nodes.top()->val);
            nodes.pop();
        }else{
            if (root->right!=nullptr)
                nodes.push(root->right);
            nodes.push(root);
            nodes.push(nullptr);
            if (root->left!=nullptr)
                nodes.push(root->left);
        }
    }
    return result;
}

后序遍历

LeetCode题解：https://www.cnblogs.com/chouxianyu/p/13293152.html

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<int> postorderTraversal(TreeNode* root) {
    stack<TreeNode*> nodes;
    vector<int> result;
    if (root!=nullptr)
        nodes.push(root);
    while(!nodes.empty()){
        root=nodes.top();
        nodes.pop();
        if(root==nullptr){
            result.push_back(nodes.top()->val);
            nodes.pop();
        }else{
            nodes.push(root);
            nodes.push(nullptr);
            if(root->right!=nullptr)
                nodes.push(root->right);
            if(root->left!=nullptr)
                nodes.push(root->left);
        }
    }
    return result;
}

参考链接

https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/mo-fang-di-gui-zhi-bian-yi-xing-by-sonp/

作者：@臭咸鱼

转载请注明出处：https://www.cnblogs.com/chouxianyu/

欢迎讨论和交流!