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

Question

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

有人能帮我吗

Answer 1

下面的代码很容易记住，因为我们只需更改（3行代码），左根右键的顺序，就像我们使用递归时所做的那样

这个问题是关于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);
}

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

        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”，这取决于您想要的顺序

示例树：

         4
        / \
       2   5
      / \   \
     1   3   7
            /
           6

…和相应的代码：

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