二叉树的前序、中序、后序、层序遍历
前序中序后序属于深度优先 / 层序属于广度优先
结点定义
1
2
3
4
5
6
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
前序遍历 - 根节点 -> 左子树根 -> 右子树根
递归法
1
2
3
4
5
6
7
8
9
vector<int> result;
void preorder(TreeNode* root)
{
if (root==NULL)
return;
result.push_back(root->val);
preorder(root->left);
preorder(root->right);
}
迭代法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> result;
void preorderTraversal(TreeNode* root) {
if (root == NULL)
return;
stack<TreeNode*> s;
s.push(root);
while (!s.empty()) {
root = s.top();
result.push_back(root->val);
s.pop();
if (root->right)
s.push(root->right);
if (root->left)
s.push(root->left);
}
}
中序遍历 - 左子树根 -> 根节点 -> 右子树根
递归法
1
2
3
4
5
6
7
8
9
vector<int> result;
void inorder(TreeNode* root)
{
if (root==NULL)
return;
inorder(root->left);
result.push_back(root->val);
inorder(root->right);
}
迭代法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> result;
void inorder(TreeNode* root)
{
stack<TreeNode*> s;
while (!s.empty() || root != NULL){
while (root != NULL){
s.push(root);
root = root->left;
}
root = s.top()->right;
result.push_back(s.top()->val);
s.pop();
}
}
后序遍历 - 左子树根 -> 右子树根 -> 根节点
递归法
1
2
3
4
5
6
7
8
9
vector<int> result;
void postorder(TreeNode* root)
{
if (root==NULL)
return;
postorder(root->left);
postorder(root->right);
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
vector<int> result;
void postorder(TreeNode* root)
{
stack<TreeNode*> s;
TreeNode* prev;
while (!s.empty() || root != NULL){
while (root != NULL){
s.push(root);
root = root->left;
}
if (s.top()->right == NULL || s.top()->right == prev){
result.push_back(s.top()->val);
prev = s.top();
s.pop();
root = NULL;
}
else{
root = s.top()->right;
}
}
}
层序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<int> result;
void levelOrder(TreeNode* root) {
if (root == NULL)
return;
queue<TreeNode*> myQueue;
myQueue.push(root);
while (myQueue.size() != 0)
{
result.push_back(myQueue.front()->val);
if (myQueue.front()->left != NULL)
{
myQueue.push(myQueue.front()->left);
}
if (myQueue.front()->right != NULL)
{
myQueue.push(myQueue.front()->right);
}
myQueue.pop();
}
}
层序遍历 - 逐层输出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<vector<int>> result;
void levelOrder(TreeNode* root) {
if (root == NULL)
return;
vector<int>* vecP = new vector<int>();
queue<TreeNode*> myQueue;
myQueue.push(root);
while (myQueue.size() != 0)
{
int size = myQueue.size();
while (size--) {
vecP->push_back(myQueue.front()->val);
if (myQueue.front()->left != NULL)
myQueue.push(myQueue.front()->left);
if (myQueue.front()->right != NULL)
myQueue.push(myQueue.front()->right);
myQueue.pop();
}
result.push_back(*vecP);
vecP = new vector<int>();
}
}