这期内容当中小编将会给大家带来有关怎样返回的python中序遍历，文章内容丰富且以专业的角度为大家分析和叙述，阅读完这篇文章希望大家可以有所收获。
【题目】
给定一个二叉树，返回它的中序 遍历。
计算
安全
数据库
网络和加速
企业服务
示例:输入: [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 = rightclass 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中序遍历了，如果刚好有类似的疑惑，不妨参照上述分析进行理解。如果想知道更多相关知识，欢迎关注亿速云行业资讯频道。
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
