时间戳

首页 > 解决方案 > 我们可以在 python 中的单个代码中编写有序、前序和后序吗？不使用递归

python - 我们可以在 python 中的单个代码中编写有序、前序和后序吗？不使用递归

问题描述

我想在 O(N) 时间复杂度和 O(N) 空间中使用单个代码（前序、后序、中序）对所有二叉树顺序进行编码，使用单个堆栈且不使用递归。

有人可以帮助我吗？

标签： pythonbinary-treeinorderpreorderpostorder

解决方案

下面的代码很容易记住，因为我们只需要更改（3 行代码） ，就像我们在使用递归时所做的那样为left-root-right排序。

有人问了 Python 实现的问题，但由于数据结构与语言无关，所以我发布了这个答案，以便其他人受益。

它是O(N)空间，使用单个堆栈并且没有递归

对于中序遍历

#include <bits/stdc++.h>
using namespace std;

struct node{
    int val;
    node *left, *right;
    node(int x) {
        val = x;
        left = right = NULL;
    }
};

void traversal_trick(node *root) {
    //inorder
    stack<pair<node*, int>> S;
    
    S.push({root, 0});
    while(!S.empty()){
        pair<node*, int> t = S.top();
        node* cur = t.first;
        int state = t.second;
        
        S.pop();

        if(cur == NULL or state == 3) continue;
        
        S.push({cur, state+1});
        
        if (state == 0) S.push({cur->left, 0});
        else if (state == 1) cout << cur->val << " " ;
        else if (state == 2) S.push({cur->right, 0});
    }
}

int main()
{
    node *root = new node(7); 
    node *t = root;
    root->left = new node(3); root->right = new node(10);
    root->left->left = new node(2); root->left->right = new node(5);
    root->left->left->left = new node(1);
    root->right->left = new node(8); 
    root->right->right = new node(12);
    
    traversal_trick(root);
}

对于Preorder Traversal：只需更改这部分代码

        if (state == 0) cout << cur->val << " " ;
        else if (state == 1) S.push({cur->left, 0});
        else if (state == 2) S.push({cur->right, 0});

对于后序遍历：只需更改这部分代码

        if (state == 0) S.push({cur->left, 0}) ;
        else if (state == 1) S.push({cur->right, 0}) ;
        else if (state == 2) cout << cur->val << " ";

有关说明，请参阅此

推荐阅读