网站说说模板.,网站维护案,wordpress权利插件,自己制作免费网站前言
科研不顺啊......又不想搞了#xff0c;随便弄弄吧#xff0c;多花点时间刷题#xff0c;今天开启二叉树#xff01;
94. 二叉树的中序遍历 - 力扣#xff08;LeetCode#xff09; 递归 # 最简单递归
class Solution:def inorderTraversal(self, root: TreeNode) …前言
科研不顺啊......又不想搞了随便弄弄吧多花点时间刷题今天开启二叉树
94. 二叉树的中序遍历 - 力扣LeetCode 递归 # 最简单递归
class Solution:def inorderTraversal(self, root: TreeNode) - List[int]:if not root:return []return self.inorderTraversal(root.left) [root.val] self.inorderTraversal(root.right)# 通用模板
class Solution:def inorderTraversal(self, root: Optional[TreeNode]) - List[int]:res [] # 收集结果def dfs(root):if not root: # 访问到空结点直接返回returndfs(root.left) # 左res.append(root.val) # 中dfs(root.right) # 右dfs(root)return res 迭代 图和代码参考王尼玛题解 class Solution:def inorderTraversal(self, root: Optional[TreeNode]) - List[int]:res []stack []while stack or root:# 不断往左子树方向走每走一次就将当前节点保存到栈中# 这是模拟递归的调用if root:stack.append(root)root root.left# 当前节点为空说明左边走到头了从栈中弹出节点并保存# 然后转向右边节点继续上面整个过程else:temp stack.pop()res.append(temp.val)root temp.rightreturn res Morris遍历 过程看官解的动图cur无左孩子说明到最左端 加入结果cur右移cur有左孩子说明有前驱找前驱 前驱无右孩生成链接、cur左移前驱有右孩断开连接记录cur结果cur右移 class Solution:def inorderTraversal(self, root: TreeNode) - List[int]:res [] # 用于存储中序遍历结果的列表cur, prev root, None # 初始化当前节点cur和前驱节点prevwhile cur: # 当前节点cur不为空时循环执行if not cur.left: # 左子树为空到最左端res.append(cur.val) # 将当前节点cur的值加入结果列表cur cur.right # 将当前节点指向右子树else:prev cur.left # 找到当前节点cur的左子树的最右节点前驱while prev.right and prev.right ! cur:prev prev.rightif not prev.right: # 如果前驱节点的右孩子为空添加连接prev.right cur # 将前驱节点的右孩子指向当前节点cur cur.left # 将当前节点移动到左子树else:prev.right None # 恢复最右节点右孩子为空res.append(cur.val) # 将当前节点cur的值加入结果列表cur cur.right # 将当前节点移动到右子树return res # 返回中序遍历结果 标记迭代 class Solution:def inorderTraversal(self, root: Optional[TreeNode]) - List[int]:res []stack [(0, root)] # 0表示当前未访问1表示已访问while stack:flag, cur stack.pop()if not cur: continueif flag 0:stack.append((0, cur.right)) # 右stack.append((1, cur)) # 中stack.append((0, cur.left)) # 左else:res.append(cur.val)return res二叉树所有遍历模板总结
144. 二叉树的前序遍历 - 力扣LeetCode
145. 二叉树的后序遍历 - 力扣LeetCode
102. 二叉树的层序遍历 - 力扣LeetCode
589. N 叉树的前序遍历 - 力扣LeetCode
后言
今天把以上几个二叉树遍历的题目模板刷熟这样后面的题才能信手拈来~
