树的迭代遍历

Posted on | Post modified: | In |
Words count in article: 601

前序遍历

在前序遍历中，根节点最先访问，因此可以直接用栈来保存需要递归访问的两个子树。右子树后访问，因此先入栈右子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> preorderTraversal(TreeNode* r) {
    vector<int> res;
    if (!r) return res;
    TreeNode * stk[1000];
    int tt = -1;
    stk[++ tt] = r;
    
    while (~tt) {
        r = stk[tt--];
        res.push_back(r->val);
        if (r->right) stk[++ tt] = r->right; // 注意入栈顺序
        if (r->left) stk[++ tt] = r->left;
    }
    return res;
}

中序遍历

在前序遍历中，因为根节点直接访问，因此不需要回溯。而中序遍历和后序遍历都需要回溯，对中序遍历而言，在回溯的过程中，按照规则若有左节点则需将左节点入栈。若刚访问了当前节点，则下一步需要访问当前节点的右节点，将右节点赋值给当前节点。这样进入下一次循环，对该右子树进行同样的操作。若该节点为空，则会弹出之前入栈的节点进行回溯，避免了重复入栈左节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> inorderTraversal(TreeNode* root) {
    vector<int> res;
    TreeNode * stk[1000];
    int tt = -1;
    TreeNode * r = root;
    // 利用空节点
    while (~tt || r) {
        while (r) {
            stk[++ tt] = r;
            r = r->left;
        }
        r = stk[tt--]; // 访问的节点都是从栈中弹出
        res.push_back(r->val);
        r = r->right; // 访问了一个节点后将其右节点赋值给它
    }
    return res;
}

后序遍历

后序遍历与中序遍历有相同的框架，只是后序需要保证先访问右节点再访问根节点。因此在对一个节点进行访问时，需要先确认当前节点无右节点或者右节点已访问。对当前节点进行访问后需要将当前节点置空，以保证下一轮迭代时的节点是从栈中弹出的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<int> postorderTraversal(TreeNode* root) {
    vector<int> res;
    if (!root) return res;
    stack<TreeNode*> st;

    while (st.size() || root) {
        while (root) {
            st.push(root);
            root = root->left;
        }
        root = st.top(); st.pop();
        // 后序访问当前节点需保证 无右节点 或 右节点已访问
        if (!root->right || (res.size() && root->right->val == res.back())) {
            // 访问当前节点
            res.push_back(root->val);
            root = nullptr;  // 需要置空避免再次访问
        }else {   
            // 先访问右子树
            st.push(root);
            root = root->right;
        }
    }
    return res;
}