1.给大家拜个年了
今天是大年初一,给大家拜个年,祝大家新的一年工作顺利、学业有成,代码越敲越顺,bug越来越少。
2.题目
这道题是2024-2-10的签到题,题目难度为简单。
考察的知识点为DFS(树的遍历)
题目链接:二叉树的中序遍历
给定一个二叉树的根节点 root
,返回 它的 中序 遍历 。
3. 思路
对于树结构的遍历,我们最早了解到这个是在数据结构里面学习的,所谓的中序遍历,以树结构为例,它是先遍历树的左子树(左子结点),然后遍历树的根结点,最后在遍历树的右子树(右子结点)。
这题我们可以定义一个空的全局变量列表,用来保存最终结果。然后定义一个函数DFS遍历这棵树,我们先递归遍历树的左节点,然后处理添加当前结点的逻辑,接着递归遍历树的右节点。最后返回这个数组就行了。
4.代码
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
# 定义结果列表
rst = []
# 中序遍历函数
def dfs(node):
# 如果当前结点不为空
# 如果当前结点有左子结点,则递归遍历
if node:
if node.left:
dfs(node.left)
# 将当前结点的值加入到结果数组
rst.append(node.val)
# 如果当前结点有右子结点,则递归遍历
if node.right:
dfs(node.right)
# 遍历根节点
dfs(root)
return rst