本期，边肖将为您带来关于如何返回的python中间顺序遍历。文章内容丰富，从专业角度进行分析和描述。希望你看完这篇文章能有所收获。
【标题】
给定一棵二叉树，返回它的顺序遍历。
示例：
输入：[1，null，2，3]
一个
\
2
/
三
输出：[1，3，2]
高级：递归算法非常简单。可以通过迭代算法做到吗？
[思考]
前序遍历、中序遍历和后序遍历。这三种遍历方式中，前、中、后是指根节点的顺序，都是先遍历左子树，再遍历右子树。
中序遍历的递归解法：先递归遍历左子树，然后访问当前节点的值，最后递归遍历右子树。
中序遍历的非递归解：使用两个栈，一个栈(栈1)存储节点，另一个栈(栈2)存储访问标签。要实现从左根到右根的顺序，需要先插入右节点，再插入根节点，最后插入左节点。步骤如下：如果堆栈1的顶部节点未被访问，弹出节点，将右边的子节点(如果有)添加到堆栈中，将节点添加到堆栈中，最后将左边的子节点(如果有)添加到堆栈中；同时，栈2添加了是否被访问的相应标签。
[代码]
python版本
递归解
# Definitionforabinarytreenode。
#classTreeNode:
#def__init__(self，val=0，left=None，right=None):
#self.val=val
#self.left=left
#自我.正确=正确
类别解决方案：
deftraverse(自我，节点):
ifnotnode:
返回
#左根右
self.traverse(节点. left)
self.res.append(node.val)
self.traverse(节点. right)
定义顺序遍历(自身，根：重新编码)-列表[int]:
self.res=[]
self.traverse(根)
returnself.res
非递归解
分类解决方案：纳米
p;
def inorderTraversal(self, root: TreeNode) -> List[int]:
'''非递归遍历'''
if not root:
return []
stack = [root]
visit = [0]
res = []
while len(stack) > 0:
# 已经遍历过，将val放到res中
if visit[-1] == 1:
res.append(stack.pop().val)
visit.pop()
# 未遍历过，则遍历左右节点（由于是栈，先保存右节点，再保存左节点）
else:
node = stack.pop()
visit_i = visit.pop()
if node.right:
stack.append(node.right)
visit.append(0)
stack.append(node)
visit.append(1)
if node.left:
stack.append(node.left)
visit.append(0)
return res
上述就是小编为大家分享的怎样返回的python中序遍历了，如果刚好有类似的疑惑，不妨参照上述分析进行理解。如果想知道更多相关知识，欢迎关注行业资讯频道。
内容来源网络，如有侵权，联系删除，本文地址：https://www.230890.com/zhan/144271.html
