Code & Func

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

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

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

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

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

先序遍历：
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
void prevorderTraversal(TreeNode *root) {
2
    if (root) {
3
        cout << root->val << endl;
4
        prevorderTraversal(root->left);
5
        prevorderTraversal(root->right);
6
    }
7
}
8

9
void inorderTraversal(TreeNode *root) {
10
    if (root) {
11
        inorderTraversal(root->left);
12
        cout << root->val << endl;
13
        inorderTraversal(root->right);
14
    }
15
}
8 collapsed lines
16

17
void postorderTraversal(TreeNode *root) {
18
    if (root) {
19
        postorderTraversal(root->left);
20
        postorderTraversal(root->right);
21
        cout << root->val << endl;
22
    }
23
}

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

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

基于栈的迭代算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

莫里斯算法

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

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

中序线索树

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

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

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

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

莫里斯算法——中序遍历

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

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

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

1
TreeNode *GetRightLeaf(TreeNode *root, TreeNode *end) {
2
    while(root->right && root->right != end) root = root->right;
3
    return root;
4
}
5

6
void inorderTraversal(TreeNode* root) {
7
    while(root) {
8
        if (root->left) {
9
            TreeNode *p = GetRightLeaf(root->left, root);
10
            if (p->right == root) {
11
                p->right = nullptr;
12
                cout << root->val << endl;
13
                root = root->right;
14
            } else {
15
                p->right = root;
8 collapsed lines
16
                root = root->left;
17
            }
18
        } else {
19
            cout << root->val << endl;
20
            root = root->right;
21
        }
22
    }
23
}

莫里斯算法——先序遍历

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

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

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

因此代码如下：

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

莫里斯遍历——后序遍历

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

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

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

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

1
TreeNode *GetRightLeaf(TreeNode *root, TreeNode *end) {
2
    while(root->right && root->right != end) root = root->right;
3
    return root;
4
}
5
TreeNode *reverse(TreeNode *p, const function<void(int)> &func) {
6
    TreeNode *prev, *next;
7
    prev = nullptr;
8
    while(p) {
9
        func(p->val);
10
        next = p->right;
11
        p->right = prev;
12
        prev = p;
13
        p = next;
14
    }
15
    return prev;
27 collapsed lines
16
}
17
vector<int> postorderTraversal2(TreeNode* root) {
18
    TreeNode node(0);
19
    node.left = root;
20
    root = &node;
21

22
    auto func1 = [&](int val) {
23
        res.push_back(val);
24
    };
25
    auto func2 = [](int val) {};
26

27
    while(root) {
28
        if (root->left) {
29
            TreeNode *p = GetRightLeaf(root->left, root);
30
            if (p->right == root) {
31
                p->right = nullptr;
32
                p = reverse(root->left, func2);
33
                reverse(p, func1);
34
                root = root->right;
35
            } else {
36
                p->right = root;
37
                root = root->left;
38
            }
39
        } else root = root->right;
40
    }
41
    return res;
42
}

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