NOTES · 学习笔记
二叉树的中序遍历
题目
二叉树是一种树形数据结构,它由节点组成,每棵二叉树有一个根节点。每个节点最多有两个子节点,分别称为左子节点和右子节点。
比如说示例 1:节点 1 是这棵树的根节点,节点 2 是根节点 1 的右子节点,根节点 1 没有左子树;节点 3 是节点 2 的左子节点,节点 2 没有右子树。
二叉树有中序遍历、前序遍历和后序遍历。它们的不同点就是根节点的位置。比如中序遍历就是 [左子树,根节点,右子树];前序遍历就是 [根节点,左子树,右子树];后序遍历就是 [左子树,右子树,根节点]。
这道题要求中序遍历,那就是 [左子树,根节点,右子树]。
我们看示例 1 这棵树,为什么输出 [1,3,2]?
我们先看根节点 1:左子树:Null,直接返回。根节点:1,记录 [1]。右子树:进入节点 2,继续遍历。
我们再看根节点 2:左子树:3,先记录 3,结果变成 [1,3]。根节点:2,记录 2,结果变成 [1,3,2]。右子树:Null,直接返回。
最后输出:[1,3,2]。
递归过程
第一步:从节点 1 开始,执行 traversal(node.Left)。节点 1 没有左子树,遇到 nil,直接返回。
接着执行 append(res, node.Val),把节点 1 加入结果:res = [1]。
第二步:遍历节点 1 的右子树,执行 traversal(node.Right),进入节点 2。节点 2 有左子树,也就是节点 3,所以先进入节点 3。
第三步:处理节点 3。节点 3 没有左子树,先记录自己:res = [1, 3]。节点 3 也没有右子树,返回节点 2。
第四步:回到节点 2。节点 2 的左子树已经遍历完了,现在记录节点 2:res = [1, 3, 2]。节点 2 没有右子树,遍历结束。
代码实现
func inorderTraversal(root *TreeNode) []int {
var res []int // 定义一个 int 类型的空切片
var traversal func(node *TreeNode) // 定义一个递归函数
traversal = func(node *TreeNode) {
if node == nil { // 如果当前节点为空,结束这次递归
return
}
traversal(node.Left) // 先遍历左子树
res = append(res, node.Val) // 将当前节点的值添加到结果切片
traversal(node.Right) // 最后遍历右子树
}
traversal(root) // 从根节点开始启动递归
return res // 返回结果
}