【力扣】94. 二叉树的中序遍历

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

提示：

• 树中节点数目在范围 [0, 100] 内
• -100 <= Node.val <= 100

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

题解：

递归法：

// 时间复杂度：O(n)
// 空间复杂度：O(n)
func inorderTraversal(root *TreeNode) []int {
	var result []int
	var inorder func(node *TreeNode)
	inorder = func(node *TreeNode) {
		if node == nil {
			return
		}
		inorder(node.Left)
		result = append(result, node.Val)
		inorder(node.Right)
	}
	inorder(root)
	return result
}

迭代法：

// 时间复杂度：O(n)
// 空间复杂度：O(n)
func inorderTraversal(root *TreeNode) []int {
	var result []int
	if root == nil {
		return result
	}
	st := list.New()
	curr := root
	for curr != nil || st.Len() > 0 {
		// 循环将所有子节点的左边都入栈
		for curr != nil {
			st.PushBack(curr)
			curr = curr.Left // 左
		}
		// 返回尾部最后一个节点并删除掉
		node := st.Remove(st.Back()).(*TreeNode)
		result = append(result, node.Val) // 中
		curr = node.Right                 // 右
	}
	return result
}

第二种迭代法：

// 时间复杂度：O(n)
// 空间复杂度：O(n)
func inorderTraversal(root *TreeNode) []int {
	var result []int
	// 创建一个栈 并将 root 节点压入栈
	stack := list.New()
	stack.PushBack(root)
	// 遍历二叉树各个节点
	for stack.Len() > 0 {
		// 取出并删除二叉树栈顶元素
		e := stack.Back()
		stack.Remove(e)
		// 栈顶元素如果为 nil，说明需要遍历当前节点
		if e.Value == nil {
			// 取出并删除下一个栈顶元素（当前节点）
			e = stack.Back()
			stack.Remove(e)
			node := e.Value.(*TreeNode)
			result = append(result, node.Val)
			continue
		}
		node := e.Value.(*TreeNode)
		// 如果右子树非空，将右子节点压入栈
		if node.Right != nil {
			stack.PushBack(node.Right)
		}
		// 压入当前节点后再压入一个 nil 做标记
		stack.PushBack(node)
		stack.PushBack(nil)
		// 如果左子树非空，将左子节点压入栈
		if node.Left != nil {
			stack.PushBack(node.Left)
		}
	}
	return result
}