微网站菜单,网站设计的主要风格,天津建站软件,免费无代码开发平台前言#xff1a;
http://t.csdnimg.cn/WzCFU#xff08;二叉树的前#xff0c;中#xff0c;后序递归与迭代法#xff09;
在前文中我们发现迭代法实现的先中后序#xff0c;其实风格也不是那么统一#xff0c;除了先序和后序#xff0c;有关联#xff0c;中序完全就…前言
http://t.csdnimg.cn/WzCFU二叉树的前中后序递归与迭代法
在前文中我们发现迭代法实现的先中后序其实风格也不是那么统一除了先序和后序有关联中序完全就是另一个风格了一会用栈遍历一会又用指针来遍历很难写出统一的代码不像是递归法实现了其中的一种遍历方式其他两种只要稍稍改一下节点顺序就可以了。
其实针对三种遍历方式使用迭代法是可以写出统一风格的代码
接下来给出统一模板下的迭代法代码及详细注释。
可能第一遍不太好理解觉得还是之前不统一的迭代写法便于理解但只需悟透一道在草稿纸上跟着代码画一遍图就吃透统一迭代法了
代码及详细注释
迭代法前序遍历
# 定义二叉树节点的类
# class TreeNode:
# def __init__(self, x):
# self.val x
# self.left None
# self.right Noneclass Solution:def preorderTraversal(self, root: Optional[TreeNode]) - List[int]:if not root:return []stack [root] # 使用栈来辅助进行遍历 把根节点root放入堆中res [] # 用于存放前序遍历的结果while stack:node stack.pop() # 弹出栈顶节点if node:if node.right:stack.append(node.right) # 先将右子节点压入栈中if node.left:stack.append(node.left) # 再将左子节点压入栈中stack.append(node) # 最后将当前节点压入栈中stack.append(None) # 压入一个空节点作为标记else:node stack.pop() # 如果弹出的是空节点说明当前节点已经遍历过了可以将其值加入结果中res.append(node.val)return res # 返回前序遍历的结果迭代法中序遍历
# 定义二叉树节点的类
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right rightclass Solution:def inorderTraversal(self, root: Optional[TreeNode]) - List[int]:if not root: # 根节点为空 返回[]return []res [] # 用于存放中序遍历的结果stack [root] # 使用栈来辅助进行遍历 把root根节点的值加入到栈中while stack:node stack.pop() # 弹出栈顶节点if node:if node.right:stack.append(node.right) # 先将右子节点压入栈中stack.append(node) # 再将当前节点压入栈中stack.append(None) # 压入一个空节点作为标记if node.left:stack.append(node.left) # 最后将左子节点压入栈中else:node stack.pop() # 如果弹出的是空节点说明当前节点已经遍历过了可以将其值加入结果中res.append(node.val)return res # 返回中序遍历的结果迭代法后序遍历
# 定义二叉树节点的类
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right rightclass Solution:def postorderTraversal(self, root: Optional[TreeNode]) - List[int]:if not root:return []res [] # 用于存放后序遍历的结果stack [root] # 使用栈来辅助进行遍历while stack:node stack.pop() # 弹出栈顶节点if node:stack.append(node) # 将当前节点压入栈中stack.append(None) # 压入一个空节点作为标记if node.right:stack.append(node.right) # 先将右子节点压入栈中if node.left:stack.append(node.left) # 再将左子节点压入栈中else:node stack.pop() # 如果弹出的是空节点说明当前节点已经遍历过了可以将其值加入结果中res.append(node.val)return res # 返回后序遍历的结果
