NOTES · 学习笔记

二叉树的中序遍历

LeetCode二叉树 · 简单约 10 分钟

题目

二叉树是一种树形数据结构,它由节点组成,每棵二叉树有一个根节点。每个节点最多有两个子节点,分别称为左子节点和右子节点。

比如说示例 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 // 返回结果
}