【力扣题解】P94-二叉树的中序遍历-Java题解

花无缺

👨‍💻博客主页：@花无缺
欢迎点赞👍 收藏⭐ 留言📝 加关注✅!
本文由 花无缺 原创

收录于专栏【力扣题解】

文章目录

【力扣题解】P94-二叉树的中序遍历-Java题解
- 🌏题目描述
- 💡题解
- 🌏总结

【力扣题解】P94-二叉树的中序遍历-Java题解

P94.二叉树的中序遍历

🌏题目描述

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

示例 1：

在这里插入图片描述

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

示例 2：

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

示例 3：

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

提示：

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

💡题解

递归法：

public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();inorder(root, res);return res;
}
public void inorder(TreeNode root, List<Integer> list) {// 节点为空, 递归终止if (root == null) {return;}// 递归遍历左子树inorder(root.left, list);// 遍历根节点list.add(root.val);// 递归遍历右子树inorder(root.right, list);
}

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

迭代法：

public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();// 空树, 返回空列表if (root == null) {return res;}// 用栈模拟模拟递归Deque<TreeNode> stack = new LinkedList<>();// 使用一个额外的辅助指针帮助我们进行中序遍历TreeNode cur = root;while (cur != null || !stack.isEmpty()) {// 指针 cur 访问到最底层的最左边的节点// 同时将访问到的所有节点入栈if (cur != null) {stack.offerLast(cur);// 左cur = cur.left;} else {cur = stack.pollLast();// 中res.add(cur.val);// 右cur = cur.right;}}return res;
}

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

🌏总结

首先我们先来了解什么是二叉树的中序遍历：二叉树的中序遍历就是按照：左子树->根节点->右子树的顺序遍历这棵二叉树。对于二叉树的操作，我们首先就会想到递归的方法。

而对于迭代法，其实也是递归思想，递归法隐式地维护了一个栈，而迭代法就是显式的维护一个栈达到模拟递归的效果。而二叉树的中序遍历的迭代法和前序遍历、后序遍历又有不一样的地方，我们知道对于二叉树的前序遍历和后序遍历，都是从根节点开始入栈并出栈，也就是说访问的节点就是我们要操作的节点，但是对于中序遍历来说就不是这样的，因为我们第一个访问的节点是根节点，但是我们首先应该是要操作左子树节点，所以中序遍历和另外两种遍历并不是完全相同的，我们需要借助一个指针先找到二叉树的最左下的节点，然后再开始迭代的操作。

作者：花无缺(huawuque404.com)