LeetCode 144. 二叉树的前序遍历

Categories:

Tags:

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

题目描述

🔥 144. 二叉树的前序遍历

思路分析

使用栈来模拟递归的过程。

初始化一个栈，将根节点压入栈中。

当栈不为空时，弹出栈顶节点，访问该节点，并将其右子节点和左子节点依次压入栈中（注意顺序，先右后左，这样出栈时先访问左子节点）。

参考代码

// 前序遍历函数
func preorderTraversal(root *TreeNode) []int {
	var res []int
	var helper func(node *TreeNode)
	helper = func(node *TreeNode) {
		if node == nil {
			return
		}
		res = append(res, node.Val) // 访问根节点
		helper(node.Left)           // 递归访问左子树
		helper(node.Right)          // 递归访问右子树
	}
	helper(root)
	return res
}

// 中序遍历函数
func inorderTraversal(root *TreeNode) []int {
	var res []int
	var helper func(node *TreeNode)
	helper = func(node *TreeNode) {
		if node == nil {
			return
		}
		helper(node.Left)           // 递归访问左子树
		res = append(res, node.Val) // 访问根节点
		helper(node.Right)          // 递归访问右子树
	}
	helper(root)
	return res
}

// 后序遍历函数
func postorderTraversal(root *TreeNode) []int {
	var res []int
	var helper func(node *TreeNode)
	helper = func(node *TreeNode) {
		if node == nil {
			return
		}
		helper(node.Left)           // 递归访问左子树
		helper(node.Right)          // 递归访问右子树
		res = append(res, node.Val) // 访问根节点
	}
	helper(root)
	return res
}

时间复杂度：O (n)，其中 n 是二叉树的节点数。每个节点被访问一次。

空间复杂度：O (n)，最坏情况下，递归栈的深度为 n。

// 前序遍历函数
func preorderTraversal(root *TreeNode) []int {
	if root == nil {
		return []int{}
	}

	var res []int
	stack := []*TreeNode{root}
	
	for len(stack) > 0 {
		node := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		res = append(res, node.Val) // 访问根节点
		if node.Right != nil {
			stack = append(stack, node.Right) // 先压入右子节点
		}
		if node.Left != nil {
			stack = append(stack, node.Left) // 再压入左子节点
		}
	}
	return res
}

时间复杂度：O (n)，其中 n 是二叉树的节点数。每个节点被访问一次。

空间复杂度：O (n)，最坏情况下，栈的大小为 n。

🍏 点击查看 Java 题解

write your code here

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/70801689