94. Binary Tree Inorder Traversal
94. Binary Tree Inorder Traversal
题目
Given the root
of a binary tree, return the inorder traversal of its nodes' values.
Example 1:
![](https://assets.leetcode.com/uploads/2020/09/15/inorder_1.jpg)
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(logn)
,最坏情况下树呈现链状,为 O(n)
。
思路二:迭代
也可以用迭代的方式实现思路一的递归函数,两种方式是等价的,区别在于递归的时候隐式地维护了一个栈,而迭代的时候需要显式地将这个栈模拟出来,其余的实现与细节都相同,具体可以参考下面的代码。
中序遍历是左中右,先访问的是二叉树顶部的节点,然后一层一层向下访问,直到到达树左面的最底部,再开始处理节点(也就是在把节点的数值放进 res 数组中),这就造成了处理顺序和访问顺序是不一致的。那么在使用迭代法写中序遍历,就需要借用指针的遍历来帮助访问节点,栈则用来处理节点上的元素。
时间复杂度:O(n)
,其中 n
是二叉树的节点数。每一个节点恰好被遍历一次。
空间复杂度:O(n)
,为迭代过程中显式栈的开销,平均情况下为 O(logn)
,最坏情况下树呈现链状,为 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;
};
相关题目
- [98. 验证二叉搜索树](./0098.md)
- [144. 二叉树的前序遍历](./0144.md)
- [145. 二叉树的后序遍历](./0145.md)
- [173. 二叉搜索树迭代器](./0173.md)
- [230. 二叉搜索树中第 K 小的元素](https://leetcode.com/problems/kth-smallest-element-in-a-bst)
- [🔒 Closest Binary Search Tree Value II](https://leetcode.com/problems/closest-binary-search-tree-value-ii)
- [🔒 Inorder Successor in BST](https://leetcode.com/problems/inorder-successor-in-bst)
- [🔒 Convert Binary Search Tree to Sorted Doubly Linked List](https://leetcode.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list)
- [783. 二叉搜索树节点最小距离](https://leetcode.com/problems/minimum-distance-between-bst-nodes)