当前位置:网站首页>二叉树的遍历(py)
二叉树的遍历(py)
2022-08-09 13:10:00 【花椒酱不吃花椒喵】
前序
# recursively
def preorderTraversal1(self, root):
res = []
self.dfs(root, res)
return res
def dfs(self, root, res):
if root:
res.append(root.val)
self.dfs(root.left, res)
self.dfs(root.right, res)
# iteratively
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
stack,ans=[root],[]
while stack:
node=stack.pop()
ans.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return ans
中序
# recursively
def inorderTraversal1(self, root):
res = []
self.helper(root, res)
return res
def helper(self, root, res):
if root:
self.helper(root.left, res)
res.append(root.val)
self.helper(root.right, res)
# iteratively
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
cur,stack,ans=root,[],[]
while stack or cur:
while cur:
stack.append(cur)
cur=cur.left
cur=stack.pop()
ans.append(cur.val)
cur=cur.right
return ans
后序
# recursively
def postorderTraversal1(self, root):
res = []
self.dfs(root, res)
return res
def dfs(self, root, res):
if root:
self.dfs(root.left, res)
self.dfs(root.right, res)
res.append(root.val)
## 标准的后序迭代
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
res = [] # 用来存储后序遍历节点的值
stack = []
node = root
while stack or node:
while node:
stack.append(node) # 第一次入栈的是根节点
#判断当前节点的左子树是否存在,若存在则持续左下行,若不存在就转向右子树
node = node.left if node.left is not None else node.right
#循环结束说明走到了叶子节点,没有左右子树了,该叶子节点即为当前栈顶元素,应该访问了
node = stack.pop() # 取出栈顶元素进行访问
res.append(node.val) # 将栈顶元素也即当前节点的值添加进res
# (下面的stack[-1]是执行完上面那句取出栈顶元素后的栈顶元素)
if stack and stack[-1].left == node: #若栈不为空且当前节点是栈顶元素的左节点
node = stack[-1].right ## 则转向遍历右节点
else:
node = None # 没有左子树或右子树,强迫退栈
return res
# iteratively2 保存节点遍历状态的迭代,和使用双栈,一个栈放node,一个栈放flag一样
class Solution:
def postorderTraversal(self, root):
traversal, stack = [], [(root, False)]
while stack:
node, visited = stack.pop()
if node:
if visited:
# add to result if visited
traversal.append(node.val)
else:
# post-order
stack.append((node, True))
stack.append((node.right, False))
stack.append((node.left, False))
return traversal
# iteratively3(前序遍历取反,最好不要用)
def postorderTraversal(self, root):
res, stack = [], [root]
while stack:
node = stack.pop()
if node:
res.append(node.val)
stack.append(node.left)
stack.append(node.right)
return res[::-1]
层序
从第一层打印到最后一层
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
ans=[]
cur_stack=[root]
while cur_stack:
next_stack,tmp=[],[]
for node in cur_stack:
tmp.append(node.val)
if node.left:
next_stack.append(node.left)
if node.right:
next_stack.append(node.right)
cur_stack=next_stack
## 如果是从最后一层打印到第一层,改成ans.insert(0,tmp)就好了
ans.append(tmp)
return ans
边栏推荐
猜你喜欢
随机推荐
程序员的七夕怎么过?不会是写代码吧
opencv-matchTemplate 之使用场景为大图里面找小图
NC96 判断一个链表是否为回文结构
海康设备获取YV12图像-不用rtsp
offset、client、scroll、window.pageYOffset比较
【面试高频题】可逐步优化的链表高频题
43. The sword refers to Offer 1 ~ 1 the number of occurrences of n integers (recursive, mathematics)
pytest 之 allure报告
面试攻略系列(三)-- 高级开发工程师面试问些啥?
FFmpeg multimedia file processing (implementation of ffmpeg operation directory and list)
现在40系显卡都快出来了,为何1060型号的显卡还有这么多人用?
微服务+微信小程序实现社区服务
力扣解法汇总1413-逐步求和得到正数的最小值
缓存和数据库一致性问题
面试攻略系列(二)-- 秒杀系统
JS轮播图实现
ArcEngine(八) 选择要素并高亮显示
Process/Thread Related in Sandbox - 2
NC53 删除链表的倒数第n个节点
学习opencv-基础应用