大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
这期内容当中小编将会给大家带来有关怎样返回的python中序遍历,文章内容丰富且以专业的角度为大家分析和叙述,阅读完这篇文章希望大家可以有所收获。
创新互联公司是专业的都昌网站建设公司,都昌接单;提供做网站、成都做网站,网页设计,网站设计,建网站,PHP网站建设等专业做网站服务;采用PHP框架,可快速的进行都昌网站开发网页制作和功能扩展;专业做搜索引擎喜爱的网站,专业的做网站团队,希望更多企业前来合作!
【题目】
给定一个二叉树,返回它的中序 遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,3,2]
进阶: 递归算法很简单,你可以通过迭代算法完成吗?
【思路】
前序遍历、中序遍历、后序遍历,这三种遍历方式中,前中后指的都是根节点的顺序,并且都是先遍历左子树、再遍历右子树。
中序遍历递归解法:先递归遍历左子树,再访问当前节点的值,最后递归遍历右子树。
中序遍历非递归解法:使用两个栈,一个栈(栈1)存储节点,另一个栈(栈2)存储访问标签。要想实现左根右的顺序,则需要先插入右节点,再插入根节点,最后插入左节点,实现步骤为:如果栈1的栈顶节点没被访问,则弹出该节点,并将右孩子节点(若有)加入栈中,将该节点加入栈,最后将左孩子节点(若有)加入栈中;同时栈2加入对应的是否被访问的标签。
【代码】
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 traverse(self, node):
if not node:
return
# 左根右
self.traverse(node.left)
self.res.append(node.val)
self.traverse(node.right)
def inorderTraversal(self, root: TreeNode) -> List[int]:
self.res = []
self.traverse(root)
return self.res
非递归解法
class Solution:
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中序遍历了,如果刚好有类似的疑惑,不妨参照上述分析进行理解。如果想知道更多相关知识,欢迎关注创新互联行业资讯频道。