树的遍历

N叉树的遍历

前序

递归版

由于LeetCode原题目要求有返回值，因此再构造一个递归函数并传递对返回结构的引用记录数值。对于N叉树的前序遍历，首先读取数值，然后从左向右依次对所有孩子结点进行递归调用。


x
1
class Solution {
2
public:
3
    void rec(Node* root, vector<int>& vpre){
4
        if(!root) return;
5
        vpre.emplace_back(root->val);
6
        for(Node* p:root->children){
7
            rec(p,vpre);
8
        }
9
    }
10
11
    vector<int> preorder(Node* root){
12
        vector<int> ans;
13
        if(!root) return ans;
14
        rec(root,ans);
15
        return ans;
16
    }
17
};

非递归

前序遍历的非递归方法需要借助栈。首先根结点入栈，然后进入循环，只要栈非空，读取栈顶结点数值并从右向左将其所有孩子结点逆序入栈，继续循环。


xxxxxxxxxx
17
1
class Solution {
2
public:
3
    vector<int> preorder(Node* root) {
4
        vector<int> ans;
5
        stack<Node*> ts;
6
        if(root) ts.push(root);
7
        while(!ts.empty()){
8
            Node* p=ts.top();
9
            ans.push_back(p->val);
10
            ts.pop();
11
            for(auto t=p->children.crbegin();t!=p->children.crend();++t){
12
                ts.push(*t);
13
            }
14
        }
15
        return ans;
16
    }
17
};

后序

递归版

先递归，再取数（值）。


xxxxxxxxxx
1
class Solution {
2
public:
3
    void rec(Node* root, vector<int> &vpost){
4
        if(!root) return;
5
        for(Node* p:root->children)
6
            rec(p,vpost);
7
        vpost.emplace_back(root->val); 
8
    }
9
10
    vector<int> postorder(Node* root){
11
        vector<int> ans;
12
        if(!root) return ans;
13
        rec(root,ans);
14
        return ans;
15
    }
16
};

非递归

这是一个有技巧的方法，先记录下来。首先根结点入栈，然后进入循环，只要栈非空，读取栈顶结点数值并从左向右依次将孩子结点入栈。这样的结果是，对任意子树，总是先获得根结点数值，再从右向左获得所有孩子结的值。因此反转获得的数值序列得到后序遍历结果。


xxxxxxxxxx
19
1
class Solution {
2
public:
3
    vector<int> postorder(Node* root){
4
        vector<int> ans;
5
        if(!root) return ans;
6
        stack<Node*> ts;
7
        ts.push(root);
8
        while(!ts.empty()){
9
            Node* p=ts.top();
10
            ans.emplace_back(p->val);
11
            ts.pop();
12
            for(Node* t:p->children){
13
                ts.push(t);
14
            }
15
        }
16
        reverse(ans.begin(),ans.end());
17
        return ans;
18
    }
19
};

层序

层序遍历需要借助队列实现。根结点入队后进入循环，首先取当前队列大小，表示一层中结点数，依次取数据并将所有孩子结点入队。


23
1
class Solution {
2
public:
3
    vector<vector<int>> levelOrder(Node* root) {
4
        vector<vector<int>> ans;
5
        if(!root) return ans;
6
        queue<Node*> q;
7
        q.push(root);
8
9
        while(!q.empty()){
10
            int cnt=q.size();
11
            vector<int> rec;
12
            for(int i=0;i<cnt;++i){
13
                Node* cur=q.front();
14
                q.pop();
15
                rec.emplace_back(cur->val);
16
                for(Node* t:cur->children)
17
                    q.emplace(t);
18
            }
19
            ans.emplace_back(rec);
20
        }
21
        return ans;
22
    }
23
};

二叉树的中序遍历

递归版


xxxxxxxxxx
1
class Solution {
2
public:
3
    void rec(Node* root, vector<int> &vin){
4
        if(!root) return;
5
        rec(root->left,vin);
6
        vin.emplace_back(root->val); 
7
        rec(root->right,vin);
8
    }
9
10
    vector<int> inorder(Node* root){
11
        vector<int> ans;
12
        if(!root) return ans;
13
        rec(root,ans);
14
        return ans;
15
    }
16
};

非递归

两种方法。

第一种，首先迭代将左孩子入栈直到没有左孩子为止，然后进入循环，只要栈非空，取栈顶数据并出栈，每当结点有右孩子时，右孩子入栈并迭代将左孩子入栈。

第二种，以根结点为当前结点，只要栈非空或当前结点存在进行循环，循环中有两部分，第一部分迭代将当前结点的左孩子入栈，第二部分取栈顶数据并出栈，使得当前结点为栈顶结点的右孩子（无论右孩子是否存在）。


x
1
class Solution {
2
public:
3
    vector<int> inorderTraversal1(TreeNode* root) {
4
        vector<int> ans; 
5
        if(!root) return ans;
6
        stack<TreeNode*> ts;
7
        ts.push(root);
8
        while(root->left){
9
            root=root->left;
10
            ts.push(root);
11
        }
12
        while(!ts.empty()){
13
            TreeNode* cur=ts.top();
14
            ans.emplace_back(cur->val);
15
            ts.pop();
16
            if(cur->right){
17
                TreeNode* t=cur->right;
18
                ts.push(t);
19
                while(t->left){
20
                    t=t->left;
21
                    ts.push(t);
22
                }
23
            }
24
        }
25
        return ans;
26
    }
27
    
28
    vector<int> inorderTraversal2(TreeNode* root) {
29
        vector<int> ans; 
30
        stack<TreeNode*> ts;
31
        TreeNode* cur=root;
32
        while(!ts.empty()||cur){
33
            while(cur){
34
                ts.push(cur);
35
                cur=cur->left;
36
            }
37
            if(!ts.empty()){
38
                cur=ts.top();
39
                ans.emplace_back(cur->val);
40
                ts.pop();
41
                cur=cur->right;
42
            }
43
        }
44
        return ans;
45
    }
46
};

参考资料

[1] 二叉树的遍历（前、中、后序及层次遍历，递归和非递归实现） - 何大土 - 博客园

→back

Contact me

Please contact me about any suggestion(s): aliceb0b@hotmail.com.