跳至主要內容

94. 二叉树的中序遍历


94. 二叉树的中序遍历

🟢   🔖  深度优先搜索 二叉树  🔗 力扣open in new window LeetCodeopen in new window

题目

Given the root of a binary tree, return the inorder traversal of its nodes' values.

Example 1:

Input: root = [1,null,2,3]

Output: [1,3,2]

Example 2:

Input: root = []

Output: []

Example 3:

Input: root = [1]

Output: [1]

Constraints:

  • The number of nodes in the tree is in the range [0, 100].
  • -100 <= Node.val <= 100

Follow up: Recursive solution is trivial, could you do it iteratively?

题目大意

给你二叉树的根节点 root ,返回它节点值的 中序 遍历。

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

解题思路

思路一:递归

中序遍历是指,对于树中的任意节点来说,先打印它的左子树,然后再打印它本身,最后打印它的右子树。而在访问左子树或者右子树的时候,按照同样的方式遍历,直到遍历完整棵树。因此整个遍历过程天然具有递归的性质,可以直接用递归函数来模拟这一过程。

  • 先递归调用 preorderTraversal(root.left) 来遍历 root 节点的左子树
  • 再将 root 节点的值加入答案
  • 最后递归调用 preorderTraversal(root.right) 来遍历 root 节点的右子树即可
  • 递归终止的条件为碰到空节点

复杂度分析

  • 时间复杂度O(n),其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。

  • 空间复杂度O(n),为递归过程中栈的开销,平均情况下为 O(log⁡n),最坏情况下树呈现链状,为 O(n)


思路二:迭代

也可以用迭代的方式实现思路一的递归函数,两种方式是等价的,区别在于递归的时候隐式地维护了一个栈,而迭代的时候需要显式地将这个栈模拟出来,其余的实现与细节都相同,具体可以参考下面的代码。

中序遍历是左中右,先访问的是二叉树顶部的节点,然后一层一层向下访问,直到到达树左面的最底部,再开始处理节点(也就是在把节点的数值放进 res 数组中),这就造成了处理顺序和访问顺序是不一致的。那么在使用迭代法写中序遍历,就需要借用指针的遍历来帮助访问节点,栈则用来处理节点上的元素。

复杂度分析

  • 时间复杂度O(n),其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。

  • 空间复杂度O(n),为迭代过程中显式栈的开销,平均情况下为 O(log⁡n),最坏情况下树呈现链状,为 O(n)

代码

递归
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function (root) {
	let res = [];
	if (root == null) return res;
	res.push(...inorderTraversal(root.left));
	res.push(root.val);
	res.push(...inorderTraversal(root.right));
	return res;
};

相关题目

题号标题题解标签难度力扣
98验证二叉搜索树[✓] 深度优先搜索 二叉搜索树 1+🟠🀄️open in new window 🔗open in new window
144二叉树的前序遍历[✓] 深度优先搜索 1+🟢🀄️open in new window 🔗open in new window
145二叉树的后序遍历[✓] 深度优先搜索 1+🟢🀄️open in new window 🔗open in new window
173二叉搜索树迭代器[✓] 设计 3+🟠🀄️open in new window 🔗open in new window
230二叉搜索树中第 K 小的元素[✓] 深度优先搜索 二叉搜索树 1+🟠🀄️open in new window 🔗open in new window
272最接近的二叉搜索树值 II 🔒 深度优先搜索 4+🔴🀄️open in new window 🔗open in new window
285二叉搜索树中的中序后继 🔒 深度优先搜索 二叉搜索树 1+🟠🀄️open in new window 🔗open in new window
426将二叉搜索树转化为排序的双向链表 🔒[✓] 深度优先搜索 4+🟠🀄️open in new window 🔗open in new window
783二叉搜索树节点最小距离[✓] 深度优先搜索 广度优先搜索 2+🟢🀄️open in new window 🔗open in new window