Diver

A coder in kindergarten

0%

树的遍历算法

发表于 更新于 分类于 ，
本文字数： 5.8k 阅读时长 ≈ 5 分钟
本文主要记录关于树的基本遍历方法。

层次遍历

使用vector

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
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        
        vector<TreeNode*> curQue;
        vector<TreeNode*> nextQue;
        vector<vector<int>> res;
        vector<int> tmp;
        int depth=0;
        
        if(!root) return res; 
        
        curQue.push_back(root);
        
        while(!curQue.empty()){
            for(int i =0; i<curQue.size(); i++){
                if(curQue[i]->left != NULL){
                    nextQue.push_back(curQue[i]->left);
                }
                if(curQue[i]->right != NULL){
                    nextQue.push_back(curQue[i]->right);
                }
                tmp.push_back(curQue[i]->val);
            }
            
            res.push_back(tmp);
            curQue = nextQue;
            depth++;
            nextQue.clear();
            tmp.clear();
        }
        
        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
25
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(!root) return res;
        vector<int> path;
        deque<TreeNode*> cur, next;
        cur.push_back(root);
        while(!cur.empty()){
            TreeNode* k = cur.front();
            cur.pop_front();
            
            path.push_back(k->val);
            if(k->left) next.push_back(k->left);
            if(k->right) next.push_back(k->right);
            
            if(cur.empty()) {
                res.push_back(path);
                path.clear();
                swap(cur, next);
            }
        }
        return res;
    }
};

上边两种方法大同小异，主要是使用的数据结构不同。

使用图（map）

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
class Solution {
private:
    
    // Map sorts by key, maintains 
    // our levels in order
    map<int, vector<int>> ourLevels;
    
    void insertAtLevel(TreeNode* root, int level) {
        if (!root) return;
        // Visit each node once, add it to our map that
        // maps nodes to their levels in the tree
        ourLevels[level].push_back(root->val);
        insertAtLevel(root->left, level + 1);
        insertAtLevel(root->right, level + 1);
        return;
    }
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ourRes;
        insertAtLevel(root, 0);
        // Go over each level in our map
        for (const auto& key : ourLevels) {
        // Push the level into our result vector
            ourRes.push_back(key.second);
        }
        return ourRes;
    }
};

使用图的方法，主要是遍历到每个节点时，保存它的层次信息在图中。

中序遍历

leetcode 94

Reference: https://www.cnblogs.com/grandyang/p/4297300.html

Recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 回溯法
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
    	// 用以存储每次访问的结点值
        vector<int> res;
        inorder(root,res);
        return res;
    }
    
private:
    void inorder(TreeNode *root, vector<int> &res){
        if(!root) return;
        if(root->left) inorder(root->left, res);
        res.push_back(root->val);
        if(root->right) inorder(root->right,res);
    }
};

w/o Recursion

方法一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> inorderTraversal(TreeNode *root) {
        vector<int> res;
        stack<TreeNode*> s;
        TreeNode* p = root;
        while(p || !s.empty()){
            while(p){
                s.push(p);
                p = p->left;
            }
            p = s.top();
            s.pop();
            res.push_back(p->val);
            p = p->right;
        }
     return res;
    }
};
方法二
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> s;
        TreeNode *p = root;
        while (!s.empty() || p) {
            if (p) {
                s.push(p);
                // 先访问跟结点，在压入栈中
                res.push_back(p->val); 
                p = p->left;
            } else {
                TreeNode *t = s.top(); s.pop();
                p = t->right;
            }
        }
        return res;
    }
};

后序遍历

leetcode: 145
Reference: https://www.cnblogs.com/grandyang/p/4146981.html

Recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 回溯法
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
    	// 用以存储每次访问的结点值
        vector<int> res;
        preorder(root,res);
        return res;
    }    
private:
    void preorder(TreeNode *root, vector<int> &res){
        if(!root) return;
        res.push_back(root->val);
        if(root->left) preorder(root->left, res);   
        if(root->right) preorder(root->right,res);
    }
};

w/o Recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> preorderTraversal(TreeNode *root) {
        vector<int> res;
        stack<TreeNode*> s;
        TreeNode* p = root;
        while(p || !s.empty()){
           if(p){
               s.push(p);
               p = p->left;
           }else{
               p = s.top();
               s.pop();
               res.push_back(p->val);
               p = p->right;
           }
        }
     return res;
    }   
};

先序遍历

Recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 回溯法
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
    	// 用以存储每次访问的结点值
        vector<int> res;
        postorder(root,res);
        return res;
    }    
private:
    void postorder(TreeNode *root, vector<int> &res){
        if(!root) return;
        if(root->left) preorder(root->left, res);   
        if(root->right) preorder(root->right,res);
        res.push_back(root->val);
    }
};

w/o Recursion

leetcode 145

Reference: https://www.cnblogs.com/grandyang/p/4251757.html

方法一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> postorderTraversal(TreeNode *root) {
        if (!root) return {};
        vector<int> res;
        stack<TreeNode*> s{{root}};
        TreeNode *head = root;
        while (!s.empty()) {
            TreeNode *t = s.top();
            if ((!t->left && !t->right) || t->left == head || t->right == head) {
                res.push_back(t->val);
                s.pop();
                head = t;
            } else {
                if (t->right) s.push(t->right);
                if (t->left) s.push(t->left);
            }
        }
        return res;
    }   
};
方法二
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if (!root) return {};
        vector<int> res;
        stack<TreeNode*> s{{root}};
        while (!s.empty()) {
            TreeNode *t = s.top(); s.pop();
            res.insert(res.begin(), t->val);
            if (t->left) s.push(t->left);
            if (t->right) s.push(t->right);
        }
        return res;
    }
};
方法三
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> s;
        TreeNode *p = root;
        while (!s.empty() || p) {
            if (p) {
                s.push(p);
                res.insert(res.begin(), p->val);
                p = p->right;
            } else {
                TreeNode *t = s.top(); s.pop();
                p = t->left;
            }
        }
        return res;
    }
};