准备工作

我们定义一个树的结点的结构体如下,

1
2
3
4
5
6
7
8
9
10
11
12
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode(int val) : val(val), left(nullptr), right(nullptr) {}

    TreeNode(int val, TreeNode *left) : val(val), left(left), right(nullptr) {}

    TreeNode(int val, TreeNode *left, TreeNode *right)
        : val(val), left(left), right(right) {}
};

定义一系列调试输出函数

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
// 美化输出一颗二叉树
void output(TreeNode *root) {
    function<void(TreeNode *, int)> f = [&](TreeNode *node, int deep) {
        if (node == nullptr) return;
        for (int i = 0; i < deep - 1; i++) cout << "    ";
        if (deep != 0) cout << "|___";
        cout << node->val << endl;
        f(node->left, deep + 1);
        f(node->right, deep + 1);
    };
    f(root, 0);
}

// 打印输出一个vector<int>
void output(vector<int> &vec) {
    for (int &v : vec) cout << v << ", ";
}

// 根据给定的策略去遍历二叉树并打印其遍历序列
void output(function<vector<int>(TreeNode *)> strategy, TreeNode *root) {
    vector<int> vec = strategy(root);
    output(vec);
}

// 根据给定的策略去遍历二叉树并打印其遍历序列并携带说明文字字符串
void output(string s, function<vector<int>(TreeNode *)> strategy,
            TreeNode *root) {
    cout << s << endl;
    output(strategy, root);
    cout << endl;
}

main函数给定如下,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int main() {
    TreeNode *root = new TreeNode(  //
        0,
        new TreeNode(1,  //
                     new TreeNode(3),
                     new TreeNode(4,                  //
                                  new TreeNode(7),    //
                                  new TreeNode(8))),  //
        new TreeNode(2,                               //
                     new TreeNode(5,                  //
                                  nullptr,            //
                                  new TreeNode(9)),
                     new TreeNode(6,  //
                                  new TreeNode(10))));
    output(root);
    output("先序遍历递归: ", preOrderTraversalRecursively, root);
    output("先序遍历非递归: ", preOrderTraversalIteratively, root);
    output("中序遍历递归: ", inOrderTraversalRecursively, root);
    output("中序遍历非递归: ", inOrderTraversalIteratively, root);
    output("后序遍历递归: ", postOrderTraversalRecursively, root);
    output("后序遍历非递归: ", postOrderTraversalIterative, root);
    return 0;
}

程序输出结果 Output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
0
|___1
    |___3
    |___4
        |___7
        |___8
|___2
    |___5
        |___9
    |___6
        |___10
先序遍历递归: 
0, 1, 3, 4, 7, 8, 2, 5, 9, 6, 10, 
先序遍历非递归: 
0, 1, 3, 4, 7, 8, 2, 5, 9, 6, 10, 
中序遍历递归: 
3, 1, 7, 4, 8, 0, 5, 9, 2, 10, 6, 
中序遍历非递归: 
3, 1, 7, 4, 8, 0, 5, 9, 2, 10, 6, 
后序遍历递归: 
3, 7, 8, 4, 1, 9, 5, 10, 6, 2, 0, 
后序遍历非递归: 
3, 7, 8, 4, 1, 9, 5, 10, 6, 2, 0,

题意分析

即我们需要实现以下的几个算法,

每个算法都是一个函数,每个函数的输入均为二叉树根节点TreeNode *root,输出为一个vector表示其遍历序列

  • 先序遍历递归算法 preOrderTraversalRecursively

  • 先序遍历非递归算法preOrderTraversalIteratively

  • 中序遍历递归算法inOrderTraversalRecursively

  • 中序遍历非递归算法inOrderTraversalIteratively

  • 后序遍历递归算法postOrderTraversalRecursively

  • 后序遍历非递归算法postOrderTraversalIterative

二叉树的基本的三种遍历

先序遍历: 先访问根节点,再访问左子树,最后访问右子树

0, 1, 3, 4, 7, 8, 2, 5, 9, 6, 10,

中序遍历: 先访问左子树,再访问根结点,最后访问右子树

3, 1, 7, 4, 8, 0, 5, 9, 2, 10, 6,

后序遍历: 先访问左子树,再访问右子树,最后访问根节点

3, 7, 8, 4, 1, 9, 5, 10, 6, 2, 0,

算法实现

递归算法

先序遍历

递归实现二叉树遍历相对比较简单,如下便为先序遍历的代码实现

1
2
3
4
5
6
void preOrderTraversal(TreeNode *node){
    if(node == nullptr) return;
    cout<<node->val<<", ";
    preOrderTraversal(node->left);
    preOrderTraversal(node->right);
}

为满足output函数实现的策略模式接口,故使用c++11的function进行封装,

1
2
3
4
5
6
7
8
9
10
11
vector<int> preOrderTraversalRecursively(TreeNode *root) {
    vector<int> ret;
    function<void(TreeNode *)> f = [&](TreeNode *node) {
        if (node == nullptr) return;
        ret.push_back(node->val);
        f(node->left);
        f(node->right);
    };
    f(root);
    return ret;
}

中序遍历, 后序遍历

同理, 仅需交换处理元素的位置,即ret.push_back(node->val);的顺序,即可实现三种不同的遍历方式.

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
// 二叉树中序遍历
vector<int> inOrderTraversalRecursively(TreeNode *root) {
    vector<int> ret;
    function<void(TreeNode *)> f = [&](TreeNode *node) {
        if (node == nullptr) return;
        f(node->left);

        ret.push_back(node->val);
        f(node->right);
    };
    f(root);
    return ret;
}



// 二叉树后序遍历
vector<int> postOrderTraversalRecursively(TreeNode *root) {
    vector<int> ret;
    function<void(TreeNode *)> f = [&](TreeNode *node) {
        if (node == nullptr) return;
        f(node->left);
        f(node->right);
        ret.push_back(node->val);
    };
    f(root);
    return ret;
}

非递归算法

先序遍历

先序遍历的基本算法流程如下,

  1. 先开辟一个栈

  2. 将根结点放入栈中

  3. 取并弹出栈顶元素t

  4. 处理该元素t

  5. 如果t的右子树不为空,那么入栈

  6. 如果t的左子树不为空,那么入栈

  7. 只要栈不为空,那么返回3

先入栈右子树是因为先序遍历需要先访问根结点,再访问左子树,再访问右子树,

再下一轮循环中,先访问栈顶元素,即栈顶元素必须是左子树才能比右子树先访问.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> preOrderTraversalIteratively(TreeNode *root) {
    vector<int> ret;
    stack<TreeNode *> st{};
    st.push(root);
    while (!st.empty()) {
        TreeNode *t = st.top();
        st.pop();
        ret.push_back(t->val);
        // 由于下一步需要访问左孩子了,
        // 故栈顶元素必须是t->left
        if (t->right != nullptr) st.push(t->right);
        if (t->left != nullptr) st.push(t->left);
    }
    return ret;
}

后序遍历

先序遍历的顺序为

根 --> 左 --> 右

后序遍历的顺序为

左 --> 右 --> 根

如果我们将先序遍历左右访问顺序交换,即得到

根 --> 右 --> 左

接下来将整个遍历结果顺序反转,即得到

左 --> 右 --> 根

简单地将先序遍历的代码修改,得到如下代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<int> postOrderTraversalIterative(TreeNode *root) {
    int arr[100];
    int len = 0;
    stack<TreeNode *> st{};
    st.push(root);
    while (!st.empty()) {
        TreeNode *t = st.top();
        st.pop();
        arr[len++] = t->val;
        // 由于下一步需要访问左孩子了,
        // 故栈顶元素必须是t->left

        if (t->left != nullptr) st.push(t->left);
        if (t->right != nullptr) st.push(t->right);
    }
    vector<int> ret;
    ret.reserve(len);
    for (int i = len - 1; i >= 0; i--) ret.push_back(arr[i]);
    return ret;
}

中序遍历

中序遍历较为复杂, 需要借助一个指针cur帮助访问结点.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<int> inOrderTraversalIteratively(TreeNode *root) {
    vector<int> ret;
    stack<TreeNode *> st;
    TreeNode *cur = root;
    while (cur != nullptr || !st.empty()) {
        if (cur != nullptr) {
            st.push(cur);
            cur = cur->left;
        } else {
            cur = st.top();
            st.pop();
            ret.push_back(cur->val);
            cur = cur->right;
        }
    }

    return ret;
}

以下面这颗树为例,

初始状态下cur指向根节点,即cur -> 5

只要还存在左孩子,就不断地向左孩子移动,每次移动都需要记录走过的根结点放入栈中,即

即cur -> 4, cur -> 1, st = {5, 4, 1}

直到左孩子为空时, 需要根据栈中的记忆进行回溯, 令栈顶弹出并赋值到cur, 此时cur就是得到的待处理的元素, 把遍历序列放到ret数组中

即cur -> 1, st = {5, 4}, ret = {1}

此时该访问cur元素的左孩子不存在, 自身已访问完毕, 该访问右孩子了, 令cur为cur的右孩子

即cur -> null, st = {5, 4}, ret = {1}

若cur不为空,则继续记录到栈中,并不断寻求左孩子.若cur为空, 则从栈中弹出元素进行回溯,

此时cur虽然为空, 但栈不为空,即可以回溯

cur-> 4, st = {5}, ret = {1, 4}

同理, 可得出余下的所有情况

cur -> 2, st={5}, ret = {1, 4}

cur -> null, st = {5, 2}, ret = {1, 4}

cur -> null, st = {5}, ret = {1, 4, 2}

cur -> 5, st = {}, ret = {1, 4, 2, 5}

cur -> 6, st = {}, ret = {1, 4, 2, 5}

cur -> null, st = {6}, ret = {1, 4, 2, 5}

cur -> null, st = {}, ret = {1, 4, 2, 5, 6}

Leetcode

现在, 你可以尝试完成leetcode上的这三道题目了

  • 144.二叉树展开为链表(二叉树的前序遍历)
  • 94.二叉树的中序遍历
  • 145.二叉树的后序遍历

参考资料

二叉树非递归遍历(先序,后序遍历) bilibili 视频

二叉树非递归遍历(中序遍历) bilibili 视频

leetcode-master/二叉树的迭代遍历.md at master · youngyangyang04/leetcode-master · GitHub