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

Question

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

有人可以帮助我吗？

Answer 1

下面的代码很容易记住，因为我们只需要更改（3 行代码），顺序为 left -root-right 就像我们在使用 recursion.

时所做的那样

问题是关于 Python 实现的，但由于数据结构是独立于语言的，我发布这个答案是为了让其他人受益。

是O(N)space，使用单栈和无递归

对于中序遍历

#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 << " ";

解释见this

Answer 2

您可以使用堆栈并为每个推送的节点附上一个顺序标识（“pre”、“in”或“post”）。然后代码可以检查这是否与所需的遍历顺序相匹配，以决定是否产生节点的值。

代码：

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

    def traversal(self, order="pre"):
        stack = [(self, "pre")]
        while stack:
            node, nodeorder = stack.pop()
            if nodeorder == order:
                yield node.value
            if nodeorder == "pre":
                stack.append((node, "in"))
                if node.left:
                    stack.append((node.left, "pre"))
            elif nodeorder == "in":
                stack.append((node, "post"))
                if node.right:
                    stack.append((node.right, "pre"))

因此 traversal 应该根据您想要的顺序将“pre”、“in”或“post”作为第二个参数。

示例树：

...以及相应的代码：

root = Node(4,
    Node(2,
        Node(1),
        Node(3)
    ),
    Node(5,
        None,
        Node(7,
            Node(6)
        )
    )
)

print(*root.traversal("pre"))   # 4 2 1 3 5 7 6
print(*root.traversal("in"))    # 1 2 3 4 5 6 7
print(*root.traversal("post"))  # 1 3 2 6 7 5 4

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

can we code inorder,preorder and postorder in single code in python ? without using recursion

python

binary-tree

inorder

preorder

postorder