94. 二叉树的中序遍历
题目:给定一个二叉树,返回它的中序遍历。
- 示例
1 | 输入: [1,null,2,3] |
进阶: 递归算法很简单,你可以通过迭代算法完成吗?
考点:
- 二叉树的中序遍历。二叉树的遍历方式分为四种:
- 中序遍历:若数为空,空操作返回,否则从根节点开始(不访问根节点),一路向下访问左子节点(一路向下的过程中也不访问节点),直到左子节点为null。
- 前序遍历
- 后序遍历
- 层序遍历
Note:中序、前序、后序均属于深度优先遍历(DFS),而层序遍历属于广度优先遍历(BFS);
- 二叉树的中序遍历。二叉树的遍历方式分为四种:
代码
我们先从简单的递归实现开始
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
if(!root) return {};
else {
inorderTraversal(root->left);
ans.push_back(root->val);
inorderTraversal(root->right);
}
return ans;
}
private:
vector<int> ans;
};
递归实现的时间复杂度为
O(N)
,因为很明显要遍历所有的元素;空间复杂度
O(N)
,平均情况为BST深度T(N)=logN
;官方给出的解题思路除了迭代法,还有利用辅助栈、莫里斯遍历
- 辅助栈:在递归实现中,我们相当于在函数调用自身的时候利用了系统虚拟内存的栈空间;而迭代实现我们要复现这一过程。
每到达一个新的节点,我们首先检查左子节点是否为null
,若不为null
则将当前节点入栈,指向左子节点;若为null
则读取自身节点值,并检查右子节点,如果右子节点为null
则出栈,读取自身节点代码如下:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
if(!root) return {};
stack<TreeNode*> stk;
vector<int> ans;
auto cur = root;
//结束条件为,栈空(BST根节点出栈或最后一个未访问节点出栈)且无右子节点(保证是最后一个节点出栈)
while(!(stk.empty() && cur==nullptr)){
while(cur != nullptr){
stk.push(cur);
cur = cur->left;//一路向下至最左
}
cur = stk.top();//触底则出栈,保存值
stk.pop();
ans.push_back(cur->val);
cur = cur->right;//接着检查右侧subtree
}
return ans;
}
};
迭代实现与递归实现时间与空间复杂度相同,均为
O(N)
;
- 莫里斯遍历:
特点在于
O(1)
的空间复杂度,缺点是会破坏二叉树结构,变成一个链表;idea: 利用线索二叉树的概念。对于一个二叉树,中序遍历最后输出的都是树的最右节点(包括根节点),极端情况是一棵二叉树只有一个节点(根节点)时,这个节点也是最后输出的节点。
从一颗二叉树的整体来看,中序遍历即为:遍历左侧树,输出根节点,遍历右侧树。
那么结合上一点,对于一个根节点,如果它左子节点不为空,那么其左子树的最右节点的后继节点为根节点,而一个最右节点必然是没有右子节点的,因此将最右节点的right指针指向其后继节点:根节点。如此,对于根节点,其左子树的一个节点指向了自己时,意味着该根节点的左子树已经遍历完了,此时可以输出根节点本身了,然后再遍历右子树。
实现:
- 对于每个节点:先假设该节点存在,那么用一个辅助指针记录以该节点的位置,用于判断该节点左子树是否遍历完成;
- 如果该节点不存在左子节点,那么输出当前节点,将当前节点更新为右子节点;如果该节点存在左子节点,找到左子树的最右节点;