二叉树的遍历

树的定义

1
2
3
4
5
struct TreeNode{
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

先序遍历

递归方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
#include<utility>
#include<vector>
#include<stack>

class Solution{
    public:
   	 	void preorder(TreeNode* root, vector<int>& result)
        {
            if(root == nullptr) return;
            result.push_back(root->val);
            preorder(root->left, result);
            preorder(root->right,result);
        };
    	vector<int> preorderTraversal(TreeNode* root)
        {
            vector<int> result;
            preorder(root,result);
            return result;
        };
    	
}

使用递归方式实现树的遍历是最简单，但是效率不是很高

实现递归方式可以分为如下几个步骤：

​ 确定递归因子 -> 确定终止条件 -> 寻找递归表达式 -> 书写程序

根据树的遍历方式，每次需要访问一个节点，因此递归因子就是树的节点

由于递归因子是节点，因此如果遍历到的节点为空时，就说明该条路已经走到尽头，需要返回

递归表达式根据树的先序遍历：中左右，

迭代方式

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
#include<iostream>
#include<utility>
#include<vector>
#include<stack>

class Solution
{
    public:
    	vector<int> preorderTraversal(TreeNode* root){
            vector<int> result;
            stack<TreeNode*> stk;
            while(root != nullptr || !stk.empty())
            {
                while(root != nullptr){
                    result.push_back(root->val);
                    stk.push(root);
                	root = root->left;
                }
               	root = stk.top();
                stk.pop();
                // 把右子树当成一颗完整的树，因此不需要在该代码之后对其进行入栈操作，
                //如果执行了入栈操作会出现空指针的情况(不应该加上stk.push(root);)
                root = root->right; 
            }
            return result;
        }
}

迭代方式实现树的遍历，根据先序遍历的特点，遍历时需要遍历到树的最左边节点，才开始遍历右边的节点，由于不知道需要遍历多少次，因此使用while循环；

只要左边的节点不为空，那么就需要我们一直遍历下去，因此终止条件可以定为root != nullptr,

当节点为空时，就需要遍历右边的子树，而右边的树也不知道有多少棵，因此还需要套上一层while循环，但是有的节点没有右孩子，如叶子节点，此时循环是不是应该结束呢？答案是否定的，为什么呢，因为在遍历右子树时，是从树的最底端开始向上开始遍历，因此如果某个节点没有右节点，不一定表示遍历结束，除非该节点是根节点。在遍历右子树时，为了能够访问所有左节点的右孩子，需要一个容器来保存访问过的这些节点，那该使用何种数据结构来存储这些遍历过的节点呢？根据先序遍历的特点，最先访问的节点的右孩子是最后访问的，因此可以想到使用栈这种数据结构，栈这种数据结构有着先进后出的特点。回到正题，那最外层的循环到底该使用什么样的条件呢，第一个条件是root != nullptr,为什么是这个条件呢？外循环是控制右子树的遍历，内循环控制左子树的遍历。只要节点不为空，就能够一直遍历到树的最右边的节点。由于遍历右子树是从树的最低端开始，如果一棵底端的树的右子树被遍历完了，不代表整棵树的右子树被遍历完了，该节点的祖先节点的右子树可能还没有遍历完，因此为了能够保证遍历整棵树，还需要加上一个条件，那就是存储节点的栈不能为空，只要栈不为空，那么栈中的节点就可能还存在右子树。综合上述条件，只有两个条件都满足时即节点空和栈为空时，才能够保证将一棵树真正的遍历完。因此在书写条件时，只要满足一个条件就可以继续执行程序。

通用方式

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
#include<iostream>
#include<utility>
#include<vector>
#include<stack>

class Solution
{
    public:
    	vector<int> preorderTraversal(TreeNode*)
        {
            vector<int> result;
            stack<pair<TreeNode*, int>> stk;
            int white = 0;
            int grey = 1;
            stk.push(make_pair(root, white));
            while(!stk.empty()){
                TreeNode* node = stk.top().first;
                int visit = stk.top().second;
                stk.pop();
                if(node == nullptr) continue;
                else if(visit == white)
                {
                    stk.push(make_pair(node->right, white));
                    stk.push(make_pair(node->left, white));
                    stk.push(make_pair(node, grey));
                }else{
                    result.push_back(node->val);
                }
            }
            return result;
        }
}

这种方式以空间为代价，从而实现各种遍历方式的统一模板。每种遍历的方式只需要更换一下遍历的顺序即可，如果是先序遍历，遍历顺序是中左右，那么入栈顺序就是右中左；如果是中序遍历，遍历顺序是左中右，那么入栈顺序就是右中左；如果是后序遍历，遍历顺序是左右中，那么入栈顺序就是中右左，即遍历顺序与入栈顺序相反。

该方式通过标记法来确定某个节点的数据是否被访问过，如果没有被访问，就继续将其左右节点进行入栈操作，否则访问该节点并将节点进行出栈。因此只要还有节点没被访问完，循环就应该继续下去，该方法中使用栈来存储节点，因此循环终止的条件就是栈不能为空；

在书写代码时。只需要改变入栈的顺序即可，标记这些都不需要进行改动。这种方式是最好记忆的

中序遍历

递归方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
#include<utility>
#include<vector>
#include<stack>

class Solution{
    public
        void inorder(TreeNode* root, vector<int>& result)
        {
            if(root == nullptr) return;
            inorder(root->left, result);
            result.push_back(root->val);
            inorder(root->right,result);
        }
    	vector<int> inorderTraversal(TreeNode* root)
        {
            vector<int> result;
            inorder(root,result);
            return result;
        };
    	
}

迭代方式

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
#include<iostream>
#include<utility>
#include<vector>
#incldue<stack>

class Solution
{
    public:
    	vetor<int> inorderTraversal(TreeNode* root)
        {
            vector<int> result;
            stack<TreeNode*> stk;
            while(root != nullptr || !stk.empty())
            {
                while(root != nullptr)
                {
                    stk.push(root);
                    root = root->left;
                }
                root = stk.top();
                result.push_back(root->val);
                stk.pop();
                root = root->right;
            }
            return result;
        }
}

通用方式

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
#include<iostream>
#include<utility>
#include<vector>
#include<stack>

class Solution
{
    public:
    	vector<int> inorderTraversal(TreeNode*)
        {
            vector<int> result;
            stack<pair<TreeNode*, int>> stk;
            int white = 0;
            int grey = 1;
            stk.push(make_pair(root, white));
            while(!stk.empty()){
                TreeNode* node = stk.top().first;
                int visit = stk.top().second;
                stk.pop();
                if(node == nullptr) continue;
                else if(visit == white)
                {
                    stk.push(make_pair(node->right, white));
                    stk.push(make_pair(node, grey));
                    stk.push(make_pair(node->left, white));
                }else{
                    result.push_back(node->val);
                }
            }
            return result;
        }
}

后序遍历

递归方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<utility>
#include<stack>
#include<vector>

class Solution
{
    public:
    	vector<int> postorderTraversal(TreeNode* root)
        {
            vector<int> result;
            stack<TreeNode*> stk;
            postorder(root, result);
            return result;
        }
    	void postorder(TreeNode* root, vector<int>& result)
        {
            if(root == nullptr) return;
            postorder(root->left, result);
            postorder(root->right, result);
           	result.push_back(root->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
29
30
31
32
33
#include<iostream>
#include<utility>
#incldue<vector>
#include<stack>

class Solution
{
    public:
    	vector<int> postorderTraversal(TreeNode* root)
        {
            vector<int> result; 
           	stack<TreeNode*> stk;
            TreeNode* pre = nullptr;
            while(root != nullptr || !stk.empty())
            {
                while(root != nullptr)
                {
                	stk.push(root);
                    root = root->left;
                }
                root = stk.top();
                if(root->right == nullptr || root->right == pre){
                    res.push_back(root->val);
                    pre = root; // 只有在访问完某个节点的右节点时才会出现回退的现象
                    stk.pop();
                    root = nullptr; // 如果不将其置为空指针，会出现重复访问的情况
                }else{
                    root = root->right;
                }
            }
            return result;
        }
}

使用迭代的方式实现树的后序遍历时，需要注意的就是如果某个节点有右孩子时，会出现访问两次的情况，因此在写代码时需要分清楚该节点是第一次被访问还是第二次被访问。同时，由于出现访问两次的情况只在访问完右节点时才出现，因此我们只需要在访问完右节点的时候进行相应的标记即可。如何进行标记呢？由于是访问完右孩子之后访问根节点，因此如果访问完右节点之后立即访问根节点，那么他们就是父子关系，可以通过这个关系进行标记。进行标记时，因为右节点优于根节点之前访问，因此需要一个变量来存储该节点用于比较。

通用方式

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
#include<iostream>
#include<utility>
#include<vector>
#include<stack>

class Solution
{
    public:
    	vector<int> postorderTraversal(TreeNode* root)
        {
            vector<int> result;
            stack<pair<TreeNode*, int>> stk;
            int white = 0;
            int grey = 1;
            stk.push(make_pair(root, white));
            while(!stk.empty()){
                TreeNode* node = stk.top().first;
                int visit = stk.top().second;
                stk.pop();
                if(node == nullptr) continue;
                else if(visit == white)
                {
                    stk.push(make_pair(node, grey));
                    stk.push(make_pair(node->right, white));
                    stk.push(make_pair(node->left, white));
                }else{
                    result.push_back(node->val);
                }
            }
            return result;
        }
}

层序遍历

从树根向树叶

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
#include<iostream>
#include<vector>
#include<queue>
#include<utility>

class Solution
{
    vector<vector<int>> levelTraversal(TreeNode* root)
    {
        vector<vector<int>> result;
        queue<TreeNode*> nodeQue;
        if(root == nullptr) return result;
        nodeQue.push(root);
        while(!nodeQue.empty())
        {
            vector<int> levelVector;
            int levelNodeNum = nodeQue.size();
            for(int i = 0; i < levelNodeNum; i++)
            {
                root = nodeQue.front();
                levelVector.push_back(root->val);
                nodeQue.pop();
                if(root->left) nodeQue.push(root->left);
                if(root->right) nodeQue.push(root->right);
            }
            result.push_back(levelVector);
        }
        return result;
    }
}

层序遍历其实是属于树的广度优先搜索(BFS)，层序遍历需要借助的结构是队列，队列这种结构的特点就是先进先出。层序遍历的思想是一层一层的访问，可以根据这个特点，手动的模拟一棵树的层序遍历，首先访问根结点，然后访问根节点的左孩子，根节点的右孩子，访问完右孩子之后，接着访问左孩子的左孩子，以此类推。要想访问所有的节点必须使用一种容器将未访问结点先存储起来，但是该使用何种容器呢？根据上面的模拟，可以发现，非常符合队列结构的特点，因此选择的存储结构就是使用队列。

从树叶到树根

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
#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
#include<queue>

class Solution
{
    public:
    	vector<vector<int>> levelOrderBottom(TreeNode* root)
        {
            vector<vector<int>> result;
            if(root == nullptr)
                return result;
            queue<TreeNode*> nodeQue;
            nodeQue.push(root);
            while(!nodeQue.empty())
            {
                vector<int> levelResult;
                int levelLen = nodeQue.size();
                for(int i = 0; i < levelLen; i++)
                {
                    levelResult.push_back(root->val);
                    if(root->left)
                        nodeQue.push(root->left);
                    if(root->right)
                       	nodeQue.push(root->right);
                    nodeQue.pop();
                    root = nodeQue.front();
                }
                result.push_back(levelResult);
            }
			reverse(result.begin(), result.end());
            return result;
        }
}

N叉树的遍历

先序遍历

递归方式

迭代方式

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
#include<iostream>
#include<stack>
#include<vector>
#include<utility>

class Solution {
public:
    vector<int> preorder(Node* root) {
            vector<int> result;
            stack<Node*> stk;
            if(root == nullptr)
                return result;
            stk.push(root);
            while(!stk.empty()) 
            {
                root = stk.top();
                stk.pop();
                result.push_back(root->val);
                int len = root->children.size();
                for(int i = len-1; i >=0; i--)
                {
                    stk.push(root->children[i]);
                }
                // root = stk.top(); 如果将16行的代码放在此处会报错，会出现访问权限的问题（野指针）的情况（栈中只有一个元素的情况下）
                
            }
            return result;


    }
};