二叉树非递归遍历(模版)

84 阅读 0 评论 56 点赞

我是靠谱客的博主天真板栗，这篇文章主要介绍二叉树非递归遍历(模版)，现在分享给大家，希望可以做个参考。

读完本篇内容大约花费您7分钟时间

本文主要讲解二叉树非递归遍历，由于是非递归遍历，所以需要用到栈stack，我们如果仔细考虑递归遍历的代码，就能明白非递归种栈的应用。

由于几种遍历方式只是在处理中间节点的时候会有不同，所以下面主要讲后序遍历，相信你看懂后对其他遍历能秒解。

leetcode145 后序遍历

先给出代码

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<int> postorderTraversal(TreeNode* root) {
    vector<int> res;
    TreeNode *p;
    if(root==nullptr) return res;
    stack<TreeNode*> s;
    s.push(root);
    while(!s.empty()){
        p=s.top();
        s.pop();
        if(p!=nullptr){
            s.push(p);
            s.push(nullptr);  //打上标记，为下次出弹出时进行处理
            if(p->right) s.push(p->right);
            if(p->left) s.push(p->left);
        }else{
            p=s.top();
            s.pop();
            res.push_back(p->val);
        }
    }
    return res;
}

我们在后序遍历时候按照左右中的顺序进行的，所以对于栈这种后进先出的结构，需要反着入节点，即先入中间节点，在入右节点，最后入左节点，这样出栈的顺序就是左右中。在入中间节点时我们给一个空标记nullptr，这样在弹出的时候如果是nullptr表示下一个节点之前已经进入栈了，现在需要进行处理，所以将下一个节点的值加入到结果集中。

好了，现在你已经知道后序遍历的写法了，那对于先序遍历，中序遍历自然也就掌握了，只需要知道遍历顺序，然后在入栈时反向入栈，并且在中节点入栈后在入一个标记位，用来告知在下次弹出的时候处理。