西宁哪家公司做网站,王野天 葛优,做网站多少钱西宁君博美评,东莞网站搜索排名CV炼丹师勇闯力扣训练营
代码随想录算法训练营第13天 二叉树的递归遍历 二叉树的迭代遍历、统一迭代 二叉树的层序遍历 一、二叉树的递归遍历#xff08;深度优先搜索#xff09;
【递归步骤】 1.确定递归函数的参数和返回值#xff1a;确定哪些参数是递归的过程中需要处理…CV炼丹师勇闯力扣训练营
代码随想录算法训练营第13天 二叉树的递归遍历 二叉树的迭代遍历、统一迭代 二叉树的层序遍历 一、二叉树的递归遍历深度优先搜索
【递归步骤】 1.确定递归函数的参数和返回值确定哪些参数是递归的过程中需要处理的那么就在递归函数里加上这个参数 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。 2.确定终止条件 写完了递归算法, 运行的时候经常会遇到栈溢出的错误就是没写终止条件或者终止条件写的不对操作系统也是用一个栈的结构来保存每一层递归的信息如果递归没有终止操作系统的内存栈必然就会溢出。 3.确定单层递归的逻辑 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程 代码如下Python二叉树的前/中/后序遍历 from typing import List# Definition for a binary tree node.
class TreeNode:def __init__(self, val0, leftNone, rightNone):self.val valself.left leftself.right right# 前序遍历-递归-LC144_二叉树的前序遍历
class Solution:def preorderTraversal(self, root: TreeNode) - List[int]:res []def dfs(node):if node is None:returnres.append(node.val)dfs(node.left)dfs(node.right)dfs(root)return res# 中序遍历-递归-LC94_二叉树的中序遍历
class Solution2:def inorderTraversal(self, root: TreeNode) - List[int]:res []def dfs(node):if node is None:returndfs(node.left)res.append(node.val)dfs(node.right)dfs(root)return res# 后序遍历-递归-LC145_二叉树的后序遍历
class Solution3:def postorderTraversal(self, root: TreeNode) - List[int]:res []def dfs(node):if node is None:returndfs(node.left)dfs(node.right)res.append(node.val)dfs(root)return res [1,2,4,5,3]1/ \2 3/ \4 5# 创建二叉树
root TreeNode(1)
root.left TreeNode(2)
root.right TreeNode(3)
root.left.left TreeNode(4)
root.left.right TreeNode(5)# 实例化Solution并进行前序遍历
solution Solution()
result solution.preorderTraversal(root)# 打印前序遍历的结果
print(result)二、二叉树的迭代遍历
三、二叉树的统一迭代
# Todo
四、二叉树的层序遍历广度优先搜索
层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。这种遍历的方式和我们之前讲过的都不太一样。
需要借用一个辅助数据结构即队列来实现队列先进先出符合一层一层遍历的逻辑而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。
而这种层序遍历方式就是图论中的广度优先遍历只不过我们应用在二叉树上。
从左到右遍历层序遍历二叉树动画如图 代码如下Python 利用长度法# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution:def levelOrder(self, root: Optional[TreeNode]) - List[List[int]]:if not root:return []queue collections.deque([root])result []while queue:level []for _ in range(len(queue)):cur queue.popleft()level.append(cur.val)if cur.left:queue.append(cur.left)if cur.right:queue.append(cur.right)result.append(level)return result
递归法# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution:def levelOrder(self, root: Optional[TreeNode]) - List[List[int]]:if not root:return []levels []def traverse(node, level):if not node:returnif len(levels) level:levels.append([])levels[level].append(node.val)traverse(node.left, level 1)traverse(node.right, level 1)traverse(root, 0)return levels
