我们可以在 python 中用单个代码编码中序、前序和后序吗?不使用递归
can we code inorder,preorder and postorder in single code in python ? without using recursion
我想在 O(N) 时间复杂度和 O(N) space 中使用单个代码(前序、后序、中序)对所有二叉树顺序进行编码,使用单个堆栈且不使用递归。
有人可以帮助我吗?
下面的代码很容易记住,因为我们只需要更改(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
您可以使用堆栈并为每个推送的节点附上一个顺序标识(“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
我想在 O(N) 时间复杂度和 O(N) space 中使用单个代码(前序、后序、中序)对所有二叉树顺序进行编码,使用单个堆栈且不使用递归。
有人可以帮助我吗?
下面的代码很容易记住,因为我们只需要更改(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
您可以使用堆栈并为每个推送的节点附上一个顺序标识(“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