微信支付 网站建设,app推广工作是做什么的,版面设计素材,建筑设计常用软件1.题目
这道题是2024-2-18的签到题#xff0c;题目难度为简单。
考察的知识点为DFS算法#xff08;树的前序遍历#xff09;。
题目链接#xff1a;N叉树的前序遍历 给定一个 n 叉树的根节点 root #xff0c;返回 其节点值的 前序遍历 。
n 叉树 在输入中按层序遍历…1.题目
这道题是2024-2-18的签到题题目难度为简单。
考察的知识点为DFS算法树的前序遍历。
题目链接N叉树的前序遍历 给定一个 n 叉树的根节点 root 返回 其节点值的 前序遍历 。
n 叉树 在输入中按层序遍历进行序列化表示每组子节点由空值 null 分隔请参见示例。 2.思路
选择哪个算法 其实对于树的遍历我们能想到常见的算法就2个BFS算法和DFS算法。BFS算法常用于树的层序遍历这种问题而DFS算法通常用于树的深度遍历前序遍历、中序遍历、后序遍历。因此这道题我们选择使用DFS算法来进行遍历。 整体思路 知道了遍历算法后我们该如何应用到这题呢我们可以定义一个递归函数dfs函数传入一个参数node类型为TreeNode我们在函数里面判断这个结点是否为空如果不为空则将当前结点的值添加到结果列表里面然后利用循环来遍历它的孩子结点列表循环里面进行dfs递归遍历。这样就能保证遍历的顺序是根-左-右。 3.代码 # Definition for a Node.
class Node:def __init__(self, valNone, childrenNone):self.val valself.children children
class Solution:def preorder(self, root: Node) - List[int]:# 如果root结点为空if not root:return []# 结果列表rst []# DFS遍历前序遍历def dfs(node):# 如果结点不为空if node:# 添加当前结点的值到结果列表里面rst.append(node.val)# 从左往右递归遍历子结点for child in node.children:dfs(child)# 遍历root结点dfs(root)return rst
