我们可以在python的一个代码中编写inorder,preorder和postorder吗?不使用递归

我想在O(N)时间复杂度和O(N)空间内对所有二叉树顺序(preorder,postorder,inorder)进行编码，使用单堆栈，不使用递归。

有人能帮我吗?

下面的代码很容易记住我们只需要改变(3行代码)， order forleft-root-right和我们使用递归时一样.

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

它是O(N)使用单栈和不带递归

ForInorder遍历

#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);
}

For预序遍历:修改这部分代码

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

ForPostorder遍历:修改这部分代码

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

有关解释，请参阅

您可以使用堆栈，并为每个推送的节点附带一个顺序标识("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的单个代码中编写order,preorder和postorder吗?不使用递归

答。是的，我们可以。首先我们初始化一个Stack [LIFO]有根和数。示例[(root,1)]数字是专门用来知道的这是我们第一次，第二次，第三次访问节点。还初始化了preorder, inorder, postorder以将答案存储在列表中

现在我们要使用的主要概念是->

循环直到堆栈不空…!(1)从栈中弹出[后进先入]出)检查数的值假设数是1在预购列表中追加根值并增加1和再次追加堆栈，如果存在左节点(root.left)，则返回也会附加到堆栈中，初始化number 1.

假设数字是2:

您将在排序列表中添加根值，并将数字增加1并在堆栈中再次追加，如果存在right(root.right)我们也会在堆栈中添加初始化

假设数字是3:

您将在postder列表中添加根值。注意*当number为3时，您不需要再次添加根，您只需弹出它。不需要检查它是否有左子树或右子树…!

就是这样，我们将使用这个逻辑来解决这个问题

Python代码→

#Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
#In one flow Striver
stack=[(root,1)]
pre,ino,post=[],[],[]
if root==None:
return
while stack:
node,nodepass=stack.pop()
if nodepass==1:
pre.append(node.val)
nodepass+=1
stack.append((node,nodepass))
if node.left!=None:
stack.append((node.left,1))
elif nodepass==2:
ino.append(node.val)
nodepass+=1
stack.append((node,nodepass))
if node.right!=None:
stack.append((node.right,1))
else:
post.append(node.val)

return pre,ino,post

你可以在练习这个问题→网站https://www.codingninjas.com/codestudio/problems/981269?topList=striver-sde-sheet-problems& utm_source = striver& utm_medium =

参考视频为了更好地理解这些概念->https://www.youtube.com/watch?v=ySp2epYvgTE

相关内容

最新更新

热门标签：