Code & Fun

今天将二叉树的先、中、后遍历的做了一些总结。三种遍历都有三种写法:

  • 递归
    • 时间复杂度:O(n)
    • 空间复杂度:O(h)h为树高
  • 基于栈进行迭代:
    • 时间复杂度:O(n)
    • 空间复杂度:O(n)
  • 莫里斯算法:
    • 时间复杂度:O(n)
    • 空间复杂度:O(1)

接下来内容有一下几个部分组成:

  1. 首先介绍二叉树先、中、后序遍历的含义
  2. 递归算法
  3. 基于栈的迭代算法
  4. 莫里斯算法

二叉树 & 先、中、后序遍历

  • 先序遍历:

    1. 访问当前节点
    2. 遍历左子树
    3. 遍历右子树
  • 中序遍历:

    1. 遍历左子树
    2. 访问当前节点
    3. 遍历右子树
  • 后序遍历:

    1. 遍历左子树
    2. 遍历右子树
    3. 访问当前节点

如上图中显示的二叉树中,先、中、后序遍历分别为:

  • 先序:1 2 3 4 5
  • 中序:3 2 4 1 5
  • 后序:3 4 2 5 1

递归算法

已知三种遍历的含义之后,我们可以很容易的写出三种遍历的递归算法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void prevorderTraversal(TreeNode *root) {
if (root) {
cout << root->val << endl;
prevorderTraversal(root->left);
prevorderTraversal(root->right);
}
}

void inorderTraversal(TreeNode *root) {
if (root) {
inorderTraversal(root->left);
cout << root->val << endl;
inorderTraversal(root->right);
}
}

void postorderTraversal(TreeNode *root) {
if (root) {
postorderTraversal(root->left);
postorderTraversal(root->right);
cout << root->val << endl;
}
}

由于递归算法比较简单,所以这里不做过多的说明。

为了方便,访问节点时,只是输出节点的值。

基于栈的迭代算法

基于栈的迭代算法——先序遍历

基于栈的遍历算法中,先序遍历是最简单的。因为先序遍历本身可以进行尾递归优化,所以很容易用stack对递归调用进行模拟:

1
2
3
4
5
6
7
8
9
10
void preorderTraversal(TreeNode *root) {
stack<TreeNode *> st;
if (root) st.push(root);
while(!st.empty()) {
root = st.top(); st.pop();
cout << root->val << endl;
if (root->right) st.push(root->right);
if (root->left) st.push(root->left);
}
}

需要注意的是,因为栈用后进先出的特性,所以要先将右子树压入栈中,然后再将左子树压入栈中。

基于栈的迭代算法——中序遍历

Binary-Tree-Preorder-Inorder-Postorder-Traversal-20200328094051-2020-03-28

我们以上图为例子,其中圆圈表示树中的节点,而三角形表示子树。其中的序号为访问顺序,我们可以发现,进行中序遍历的二叉树都符合这样的移动规律:

  1. 先一直往左孩子的方向移动,直到没有左孩子。
  2. 然后访问该节点,并遍历其右子树(这时相当于对其右子树进行 1、2、3步)。
  3. 最后返回到其父节点并从第 2 步开始。

为了方便实现和代码的简洁,我们可以把观察到规律转换一下:

  1. 先一直往左孩子的方向移动,直到当前节点为空,同时把所有经过的节点压入栈中。
  2. 如果栈不空,则将栈顶弹出并访问,向右孩子移动并返回第一步。

因此我们可以写出如下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
void inorderTraversal(TreeNode *root) {
stack<TreeNode *> st;
while(root || !st.empty()) {
while(root) {
st.push(root);
root = root->left;
}
// 栈一定不为空
root = st.top(); st.pop();
cout << root->val << endl;
root = root->right;
}
}

基于栈的迭代算法——后序遍历

Binary-Tree-Preorder-Inorder-Postorder-Traversal-20200328094135-2020-03-28

后序遍历与中序遍历有些类似,同样需要先一直往左孩子方向移动直到没有左孩子,但是后序遍历要先访问完右子树才能访问当前节点,因此对于栈顶节点是否要访问并弹出,我们需要判断其右子树是否被访问了。同时,因为后序遍历中,一颗树的根节点是最后访问的,所以我们可以根据右孩子是否被访问了来判断右子树是否被访问了。而我们知道,当访问完右孩子,就可以马上访问该节点了,所以我们可以维护一个指针,该指针指向上一次被访问的节点。通过判断上一次被访问的节点是否为右子树或者nullpter,我们就可以知道是否要访问该节点并弹栈了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void postorderTraversal(TreeNode* root) {
TreeNode *prev = nullptr;
stack<TreeNode *> st;
while(root || !st.empty()) {
while(root) {
st.push(root);
root = root->left;
}
root = st.top();
if (root->right == nullptr || root->right == prev) {
cout << root << right << endl;
prev = root;
root = nullptr;
st.pop();
} else root = root->right;
}
return res;
}

莫里斯算法

莫里斯算法是一种用时间来换空间的二叉树遍历算法。他只需要O(1)的空间复杂度。

个人觉得它非常像中序线索树,所以我们先介绍中序线索树,然后再来理解莫里斯遍历。

中序线索树

假设一颗二叉树有N个节点,因为每个节点有 2 个指向孩子的指针,所以我们就有了 2*N 个指向节点的指针。同时,因为根节点不需要指针指向它,所以我们就使用了2*N - (N-1) = N + 1个空指针。线索树的想法就是将这些空指针利用上,来加快遍历速度的。

Binary-Tree-Preorder-Inorder-Postorder-Traversal-20200328104922-2020-03-28

对于上面的二叉树来说,其中序遍历的结果为[6 4 7 2 5 8 9 1 3]

如果节点 A 被访问后,马上访问 B,我们就认为 A 是 B 的前驱,B 是 A 的后继。从中序遍历的结果可以看出 6 是 4 的前驱,4 是 6 的后继。

Binary-Tree-Preorder-Inorder-Postorder-Traversal-20200328105557-2020-03-28

上图中,红色虚线表示后继,绿色虚线表示前驱,一般我们将前驱放在左孩子,后继放在右孩子中。为了区分一个节点的两个孩子指针到底是真的孩子,还是线索,一般需要在每个节点中增加两个flag 位来区分。

莫里斯算法——中序遍历

因为中序线索树需要给每个节点都增加两个flag,但是因为很多时候我们不能修改二叉树节点的数据结构,所以它在很多情况是不适合的。通过观察我们可以发现,在建立完中序线索树后,一个节点的左子树中最右边的节点的后继线索是总指向该节点的。我们可以根据这个规律来判断当前节点是否需要访问,是向左孩子移动还是向右孩子移动。同时,因为遍历时不需要用到前驱,所以我们不用建立前驱的节点,只需要建立后继即可。

Binary-Tree-Preorder-Inorder-Postorder-Traversal-20200328112150-2020-03-28

当我们访问节点root的时候:

  • 如果它有左孩子,则找出左子树中最右边节点,并将该节点的右孩子设置为root(建立线索),并向左孩子移动。
  • 如果它有左孩子,同时在找出左子树最右边节点的时候,如果发现某个节点的右孩子为root,则表示为该节点为左子树的最右边的节点,且已经建立了线索。这表示我们已经访问过左子树了。我们可以清除线索,访问root节点,并向右子树移动。
  • 如果它没有左孩子,则直接访问root,并向右子树移动。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
TreeNode *GetRightLeaf(TreeNode *root, TreeNode *end) {
while(root->right && root->right != end) root = root->right;
return root;
}

void inorderTraversal(TreeNode* root) {
while(root) {
if (root->left) {
TreeNode *p = GetRightLeaf(root->left, root);
if (p->right == root) {
p->right = nullptr;
cout << root->val << endl;
root = root->right;
} else {
p->right = root;
root = root->left;
}
} else {
cout << root->val << endl;
root = root->right;
}
}
}

莫里斯算法——先序遍历

在莫里斯算法中,先序遍历与中序遍历非常想,只是访问root的节点的位置变了。在中序遍历中,我们总是在向右子树移动的时候访问root节点。而在先序遍历的中,我们总是在向左子树移动的时候访问root。当然,在没有左孩子的情况时,一样也是先访问root节点,再想右孩子移动。

当我们访问节点root的时候:

  • 如果它有左孩子,则找出左子树中最右边节点,并将该节点的右孩子设置为root(建立线索),访问root节点,并向左孩子移动。
  • 如果它有左孩子,同时在找出左子树最右边节点的时候,如果发现某个节点的右孩子为root,则表示为该节点为左子树的最右边的节点,且已经建立了线索。这表示我们已经访问过左子树了。我们可以清除线索,并向右子树移动。
  • 如果它没有左孩子,则直接访问root,并向右子树移动。

因此代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
TreeNode *GetRightLeaf(TreeNode *root, TreeNode *end) {
while(root->right && root->right != end) root = root->right;
return root;
}
void preorderTraversal(TreeNode* root) {
while(root) {
if (root->left) {
// if (root->right == nullptr) cout << "NULL" << endl;
TreeNode *p = GetRightLeaf(root->left, root);
if (p->right == root) {
p->right = nullptr;
root = root->right;
} else {
p->right = root;
cout << root->val << endl;
root = root->left;
}
} else {
cout << root->val << endl;
root = root->right;
}
}
}

莫里斯遍历——后序遍历

Binary-Tree-Preorder-Inorder-Postorder-Traversal-20200328115304-2020-03-28

通过观察,我们可以发现先、中、后序遍历有上面这种规律,因此我们可以发现,当所有左子树被访问完了(这时只剩下一条由右孩子组成的边,这里为了简便,将其称为,右边),按逆序访问由右边即可。

当我们访问节点root的时候:

  • 如果它有左孩子,则找出左子树中最右边节点,并将该节点的右孩子设置为root(建立线索),并向左孩子移动。
  • 如果它有左孩子,同时在找出左子树最右边节点的时候,如果发现某个节点的右孩子为root,则表示为该节点为左子树的最右边的节点,且已经建立了线索。这表示我们已经访问过左子树了。我们可以清除线索,逆序访问左子树的右边。
  • 如果它没有左孩子,并向右子树移动。

按上面的算法进行的话,会导致有一条右边没办法访问到,所以增加一个虚节点,该虚节点的左孩子为root,右孩子为空,即:

Binary-Tree-Preorder-Inorder-Postorder-Traversal-20200328120751-2020-03-28

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
30
31
32
33
34
35
36
37
38
39
40
41
42
TreeNode *GetRightLeaf(TreeNode *root, TreeNode *end) {
while(root->right && root->right != end) root = root->right;
return root;
}
TreeNode *reverse(TreeNode *p, const function<void(int)> &func) {
TreeNode *prev, *next;
prev = nullptr;
while(p) {
func(p->val);
next = p->right;
p->right = prev;
prev = p;
p = next;
}
return prev;
}
vector<int> postorderTraversal2(TreeNode* root) {
TreeNode node(0);
node.left = root;
root = &node;

auto func1 = [&](int val) {
res.push_back(val);
};
auto func2 = [](int val) {};

while(root) {
if (root->left) {
TreeNode *p = GetRightLeaf(root->left, root);
if (p->right == root) {
p->right = nullptr;
p = reverse(root->left, func2);
reverse(p, func1);
root = root->right;
} else {
p->right = root;
root = root->left;
}
} else root = root->right;
}
return res;
}

为了使得空间复杂度为O(1),在逆序访问时,我们通过“翻转链表”的方式进行逆序访问,而不是用栈来实现。


本文首发于Code & Fun