94. Binary Tree Inorder Traversal

94. Binary Tree Inorder Traversalopen 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;
};

迭代

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function (root) {
	let res = [];
	if (root == null) return res;
	let stack = [];
	let cur = root;
	while (cur != null || stack.length) {
		if (cur != null) {
			stack.push(cur);
			cur = cur.left;
		} else {
			cur = stack.pop();
			res.push(cur.val);
			cur = cur.right;
		}
	}
	return res;
};

94. Binary Tree Inorder Traversal

# 94. Binary Tree Inorder Traversalopen in new window

# 题目

# 题目大意

# 解题思路

# 思路一：递归

# 思路二：迭代

# 代码

# 相关题目

94. Binary Tree Inorder Traversalopen in new window

题目

题目大意

解题思路

思路一：递归

思路二：迭代

代码

相关题目