二叉树的遍历

遍历是对树的一种最基本的操作。本文使用非递归方式实现对二叉树的前序遍历、中序遍历、后序遍历、层级遍历。其实能用递归方法做的,都可以通过自己的数据结构来代替函数栈。

前序遍历

Binary Tree Preorder Traversal

对于 p 点,先将 p 点的值加入结果中,然后一次对左右孩子(如果有)进行入栈操作。

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

中序遍历

Binary Tree Inorder Traversal

需要先将所有左孩子压入栈中,所以对于 p 点有:

  1. 如果左孩子不为空,那么将 p 点压入栈中,然后 p 指向 p 的左孩子。
  2. 如果左孩子为空,意味着到了树叶,进行出栈操作。输出 p 的值。p 指向 p 的右孩子 p->right。
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> inorderTraversal(TreeNode* root) {
stack<TreeNode*> s;
vector<int> result;
TreeNode* p = root;
while(p!=NULL || !s.empty()){
if(p!=NULL){
s.push(p);
p = p->left;
}else{
p = s.top();
s.pop();
result.push_back(p->val);
p = p->right;
}
}
return result;
}
};

后序遍历

Binary Tree Postorder Traversal

对于 p 点,有两种情况可以输出它的值。其他情况下,需要依次把它的右孩子以及左孩子压入栈中。

  1. 它没有左右孩子。
  2. 它有左右孩子,但是它的左右孩子已经被访问了。
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
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> s;
vector<int> result;
TreeNode* p = root;
TreeNode* pre = NULL;
if (root == NULL){
return {};
}
s.push(p);
while(!s.empty()){
p = s.top();
if((p->left==NULL && p->right==NULL)||
(pre!=NULL&&(pre==p->right||pre==p->left))){
result.push_back(p->val);
s.pop();
pre = p;
}else{
if(p->right!=NULL){
s.push(p->right);
}
if(p->left!=NULL){
s.push(p->left);
}
}
}
return result;
}
};

层次遍历

Binary Tree Level Order Traversal

因为打印结果是按照进入顺序来输出,所以这里使用队列。每次将每一层的点压入队列中,然后依次加到临时结果中。同时还需要把下一层的点也加入队列中。

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 {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> result;
if (root == NULL){
return result;
}
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
vector<int> tmp;
int size = q.size();
while(size--){
TreeNode* e = q.front();
q.pop();
tmp.push_back(e->val);
if(e->left){
q.push(e->left);
}
if(e->right){
q.push(e->right);
}
}
result.push_back(tmp);
}
return result;
}
};

Binary Tree Level Order Traversal II

只需要在上面的基础上,将 result 数组反转一下即可。

1
reverse(result.begin(), result.end());