给定一个二叉树的根节点 root
,返回它的 中序 遍历。
递归遍历和非递归遍历应该牢牢背熟。
递归遍历
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| class Solution { public: void inorder(TreeNode * root, vector<int>& res) { if(root == nullptr) { return ; } inorder(root->left, res); res.push_back(root->val); inorder(root->right, res); } vector<int> inorderTraversal(TreeNode* root) { vector<int> res; inorder(root, res); return res; } };
|
非递归遍历
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| class Solution { public: vector<int> inorderTraversal(TreeNode* root) { stack<TreeNode *> s; vector<int> res; TreeNode * p = root; while (p || !s.empty()) { if(p) { s.push(p); p = p->left; } else { p = s.top(); res.push_back(p->val); s.pop(); p = p->right; } } return res; } };
|
Morris 中序遍历
Morris 遍历算法可以将非递归的中序遍历空间复杂度降为O(1)。
假设当前遍历节点为x,步骤为:
- 如果 x 无左孩子,加入答案数组,接着访问x右孩子
- 如果 x 有左孩子,就找到 x 左子树上最右的节点(即 左子树中序遍历的最后一个节点,x在中序遍历中的前驱节点),记为 predecessor。根据predecessor的右孩子是否为空,进行操作:
- 如果predecessor的右孩子为空,则将右孩子指向x,然后访问x的左孩子
- 如果右孩子不为空,则该右孩子一定指向x(因为predecessor一定是x的左子树的最右节点,所以若右孩子不为空则一定是指向x),这是说明已遍历完x的左子树,那么就将predecessor的右孩子置空,将x加入答案数组,然后访问x的右孩子
重复操作,直至遍历完整棵树。
在整个过程,其实多做了一步:假设当前遍历到节点为x,将x的左子树的最右节点指向x,这样当左子树遍历完后就通过这个指向走回x,且通过这个指向可以知道已经遍历完了左子树,不需要栈来维护。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
| class Solution { public:
vector<int> inorderTraversal(TreeNode* root) { vector<int> res; TreeNode * p = root; while (p) { if(p->left) { TreeNode * predecessor = p->left; while (predecessor->right && predecessor->right != p) { predecessor = predecessor->right; } if(predecessor->right == nullptr) { predecessor->right = p; p = p->left; } else { predecessor->right = nullptr; res.push_back(p->val); p = p->right; } } else { res.push_back(p->val); p = p->right; } }
return res; } };
|
性能分析
时间复杂度:每个节点都访问了两个,所以为O(n)。
空间复杂度:O(1)。
颜色标记法
来自评论。
算法思想
中序遍历,即每个节点在第二次访问的时候会被输出。因此可以使用任何东西来记录节点的访问次数,当第二次被访问的时候就输出。
因此可以使用颜色,或者使用哈希表来记录。
用白色表示从未被访问过的节点,用灰色表示已被访问过一次。
则:
- 当访问到的节点为白色时,则标记为灰色,然后依次将它的右子结点,它自己,左子结点 进栈
- 如果访问到的节点为灰色时,则添加到答案数组中,即输出
初始时,将根节点标记为白色,然后进栈。
然后循环出栈即可。
这种方式可以对于前序、后序、中序写出一致的代码。
注意
因为前序遍历顺序为:中 左 右
中序遍历顺序为:左 中 右
后序遍历顺序为:左 右 中
而栈是先进后出,所以中序遍历时,反过来,加入栈的顺序是:右子结点、自己、左子结点。
同样,如果是 前序遍历那么加入栈的顺序应为:右子结点、左子结点、自己。
算法实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
| class Solution { public:
vector<int> inorderTraversal(TreeNode* root) { vector<int> res; stack<pair<TreeNode *, int>> s; s.push(make_pair(root, 0)); while (!s.empty()) { pair<TreeNode *, int> node = s.top(); s.pop(); if(node.first == nullptr) { continue; } if(node.second == 0) { s.push(make_pair(node.first->right, 0)); s.push(make_pair(node.first,1)); s.push(make_pair(node.first->left, 0)); } else { res.emplace_back(node.first->val); } } return res; } };
|
性能分析
时间复杂度:O(n)。
空间复杂度:O(n)。