c++二叉树遍历-从递归法到迭代法的前世今生

写这个博客的起因

最开始写算法就是为了刷题而刷题， 最终刷完一遍之后忘记得差不多了， 现在写些算法完全是觉得有趣。
前几天写了个c++ 二叉树遍历for loop统一迭代法
觉得写的还不错， 后面想了想，这递归到迭代到底是如何演变过来的了
本文是模拟系统栈递归调用实现的，从他的实现你可以看到通用的迭代法的影子；
talk is cheap, here is the code!

二叉树的定义

using VALUE_TYPE  = int;
struct TreeNode {
    explicit TreeNode(const VALUE_TYPE &val, TreeNode *left = nullptr, TreeNode *right = nullptr) : val(val),
                                                                                                    left(left),
                                                                                                    right(right) {}
    VALUE_TYPE val{};
    struct TreeNode *left{}, *right{};

};
1
2
3
4
5
6
7
8
9

前序遍历递归代码

class Solution {
public:
    void preorderTraversal_recursion_helper(TreeNode *currentFrame, vector<int> &data) {
        if (nullptr == currentFrame) {
            return;
        }
        // 当前frame还未添加到data
        data.push_back(currentFrame->val); // 0
        // currentFrame 入栈位置, 这里的栈值的系统栈， 我们自己用栈模拟的时候需要用栈实际操作
        preorderTraversal_recursion_helper(currentFrame->left, data); // 1
        preorderTraversal_recursion_helper(currentFrame->right, data); // 2
        // 3
        // currentFrame 出栈位置
    }

    vector<int> preorderTraversal_recursion(TreeNode *root) {
        vector<int> ans;
        preorderTraversal_recursion_helper(root, ans);
        return ans;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

第一代模拟代码，前序遍历递归—> 用栈迭代

说明：

1. Item 代表的是一个节点的状态
   t = 0, 节点还未访问过
   t = 1, 节点的左节点还未访问过
   t = 3 节点的右节点还未被访问过
2. 读迭代法代码的时候请和递归法对照着看

class Solution {
public:
    void preorderTraversal_recursion_helper(TreeNode *root, vector<int> &data) {
        if (nullptr == root) {
            return;
        }
        data.push_back(root->val);  // 0
        // 入栈
        preorderTraversal_recursion_helper(root->left, data); // 1
        preorderTraversal_recursion_helper(root->right, data); // 2
        // 出栈 // 3
    }

    vector<int> preorderTraversal_recursion(TreeNode *root) {
        vector<int> ans;
        preorderTraversal_recursion_helper(root, ans);
        return ans;
    }

    struct Item {
        // t = 0 入栈的状态
        // t = 1 第一次访问
        // t = 2 第二次访问
        // t = 3 第三次访问
        int t{};
        TreeNode *node;
    };

    vector<int> preorderTraversal_stack(TreeNode *root) {
        vector<int> ans;
        if (nullptr == root) {
            return ans;
        }
        stack<Item> st;
        Item cur{0, root};
        //add(st, ans, root);
        while (cur.node || !st.empty()) {
            if (!cur.node) {
                cur = st.top();
                st.pop();
            }
            if (0 == cur.t) {   // 0
                ans.push_back(cur.node->val);
            }
            ++cur.t;
            if (1 == cur.t) {
                // 还不能出栈， 修改完状态重新入栈
                if (cur.node->left) { // 1
                    Item item{.t = 0, cur.node->left};
                    st.push(cur);
                    cur = item;
                }
                continue;
            }
            if (2 == cur.t) {
                if (cur.node->right) { // 2
                    Item item{.t = 0, cur.node->right};
                    st.push(cur);
                    cur = item;
                }
                continue;
            }
            if (3 == cur.t) { // 3
                cur.node = nullptr;
                continue;
            }
        }
        return ans;
    }
};
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

最终代码 前中后序代码的统一迭代法

enum Order{
    Pre_Order = 0,
    In_Order = 1,
    Post_Order = 2
};

class Solution {
public:
    constexpr static TreeNode* TreeNode::*next_child[3] = {&TreeNode::left, &TreeNode::right, nullptr};
    struct Frame {
        TreeNode *node;
        int t;

        explicit Frame(TreeNode* node = nullptr, int t = -1) :node(node), t(t){}

        TreeNode* TreeNode::* getNextChild() {
            t++;
            if (t > 2) {
                t = 2;
            }
            return next_child[t];
        }
    };

    vector<int> traversal_simulate_stack(TreeNode *root, Order order = Pre_Order) {
        vector<int> ans;
        if (nullptr == root) {
            return ans;
        }
        stack<Frame> st;
        Frame currentFrame{root};
        while (currentFrame.node || !st.empty()) {
            if (!currentFrame.node) {
                currentFrame = st.top();
                st.pop();
            }
            auto child = currentFrame.getNextChild();
            // order == Pre_Order 先序遍历
            // order == In_Order 中序遍历
            // order == Post_Order 后序遍历
            if (child == next_child[order]) {
                ans.push_back(currentFrame.node->val);
            }
            if (child) {
                if (currentFrame.node->*child) {
                    Frame frame{currentFrame.node->*child};
                    st.push(currentFrame);
                    currentFrame = frame;
                }
                continue;
            }
            currentFrame.node = nullptr;
        }
        return ans;
    }
};

int main() {
    auto pre = Solution{}.traversal_simulate_stack(makeTree(), Pre_Order);
    cout << "Pre_Order:\t";
    for (auto v : pre) {
        cout << v << "\t";
    }
    cout << endl;

    cout << "In_Order:\t";
    auto in = Solution{}.traversal_simulate_stack(makeTree(), In_Order);
    for (auto v : in) {
        cout << v << "\t";
    }
    cout << endl;

    cout << "Post_Order:\t";
    auto post = Solution{}.traversal_simulate_stack(makeTree(), Post_Order);
    for (auto v : post) {
        cout << v << "\t";
    }
}
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

输出

后记

  多思考， 多思考， 希望有问题能积极沟通
1