LeetCode 94. 二叉树的中序遍历

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

✅ 94. 二叉树的中序遍历

思路分析

中序遍历的顺序是：左子树 -> 根节点 -> 右子树。

参考代码

// 前序遍历
func preorderTraversal(root *TreeNode) []int {
	var res []int

	var dfs func(node *TreeNode)
	dfs = func(node *TreeNode) {
		if node == nil {
			return
		}
		res = append(res, node.Val) // 根
		dfs(node.Left)              // 左
		dfs(node.Right)             // 右
	}

	dfs(root)
	return res
}

// 中序遍历
func inorderTraversal(root *TreeNode) []int {
	var res []int

	var dfs func(node *TreeNode)
	dfs = func(node *TreeNode) {
		if node == nil {
			return
		}
		dfs(node.Left)              // 左
		res = append(res, node.Val) // 根
		dfs(node.Right)             // 右
	}

	dfs(root)
	return res
}

// 后序遍历
func postorderTraversal(root *TreeNode) []int {
	var res []int

	var dfs func(node *TreeNode)
	dfs = func(node *TreeNode) {
		if node == nil {
			return
		}
		dfs(node.Left)              // 左
		dfs(node.Right)             // 右
		res = append(res, node.Val) // 根
	}

	dfs(root)
	return res
}

func inorderTraversal(root *TreeNode) []int {
	var res []int
	var stack []*TreeNode
	cur := root

	for cur != nil || len(stack) > 0 {
		// 一直向左走，直到没有左子节点
		for cur != nil {
			stack = append(stack, cur)
			cur = cur.Left
		}

		// 弹出栈顶节点
		cur = stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		res = append(res, cur.Val)

		// 访问右子节点
		cur = cur.Right
	}

	return res
}

时间复杂度：O (n)，其中 n 是二叉树的节点数。

空间复杂度：O (h)，其中 h 是二叉树的高度。

➡️ 点击查看 Java 题解

write your code here

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/62975418