LeetCode 94. 二叉树的中序遍历

Categories:

Tags:

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

题目描述

🔥 94. 二叉树的中序遍历

思路分析

中序遍历的顺序是：左子树 -> 根节点 -> 右子树。我们可以使用迭代的方法来实现中序遍历，具体步骤如下：

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

初始化一个指针 cur 指向根节点。

将左子树的节点依次压入栈中，直到 cur 为空。

弹出栈顶节点，将其值加入结果列表，并将 cur 指向其右子树。

重复步骤 3 和 4，直到栈为空且 cur 为空。

参考代码

// 前序遍历函数
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 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 是二叉树的高度。最坏情况下，栈的空间复杂度为 O (n)，在树呈现链状时。

🍏 点击查看 Java 题解

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (!stack.isEmpty() || cur != null) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode node = stack.pop();
            res.add(node.val);
            cur = node.right;
        }
        return res;
    }
}

本文作者: HGNULB

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