binary tree traversal
There are four types: prelude, intermediate, subsequent, and stratified
where the front-middle-back order belongs to depth-first search and the layer order belongs to breadth-first search
Pre-order traversal order:
Root node - > left subtree - > right subtree
Mid-order traversal order:
Left subtree - > root node - > right subtree
Posterior traversal order:
Left subtree - > Right subtree - > Root node
It's not hard to realize that the front-middle-back is actually the position of the root node in the traversal
As for hierarchical traversal, as the name implies, it is a layer-by-layer traversal from left to right
Recursive traversal (before, during and after)
- Determine the parameters and return value of the recursive function: because to print out the value of the previous traversal of the node, so the parameters need to be passed into the vectors to put the value of the node, in addition to this there is no need to deal with what the data does not need to have a return value, so the recursive function return type is void.
- Determine the termination conditions: in the process of recursion, how to be considered the end of the recursion, of course, is the current traversal of the node is empty, then the recursion will be the end of this level, so if the current traversal of this node is empty, it is directly RETURN.
- Determine the logic of single-level recursion: the preorder traversal is a middle-right-left order, so the logic in single-level recursion is to take the value of the middle node first.
Upper code (●'◡'●)
Preface:
class Solution {
public:
void traversal(TreeNode* cur, vector<int>& vec) {
if (cur == NULL) return;
vec.push_back(cur->val); // center
traversal(cur->left, vec); // unorthodox
traversal(cur->right, vec); // right (-hand)
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
traversal(root, result);
return result;
}
};
Mid-sequence:
class Solution {
public:
void traversal(TreeNode* cur, vector<int>& vec) {
if (cur == NULL) return;
traversal(cur->left, vec); // unorthodox
vec.push_back(cur->val); // center
traversal(cur->right, vec); // right (-hand)
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
traversal(root, result);
return result;
}
};
Post-sequence:
class Solution {
public:
void traversal(TreeNode* cur, vector<int>& vec) {
if (cur == NULL) return;
traversal(cur->left, vec); // unorthodox
traversal(cur->right, vec); // right (-hand)
vec.push_back(cur->val); // center
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
traversal(root, result);
return result;
}
};
Iterative traversal (before, during and after)
The underlying implementation of recursion is actually a stack
So we can use a stack to implement a binary tree traversal in pre-middle and post order
But since it can be cumbersome and the three traversals can't be harmonized, let's look at another approach:
With a stack, you can't solve the inconsistency between accessing nodes (traversing them) and processing them (putting elements into the result set) at the same time.
Then we'll put the nodes we visit on the stack, and put the nodes we want to process on the stack as well but mark them.
How to mark it is to put a null pointer as a marker immediately after the node to be processed is put on the stack. This method can also be called the marking method.
You can see that we add the accessed node directly to the stack, but if it is a processed node we put an empty node after it, so that only when the empty node pops up, the next node is put into the result set.
Upcode (●'◡'●)
Preface:
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
if (root != NULL) (root);
while (!()) {
TreeNode* node = ();
if (node != NULL) {
();
if (node->right) (node->right); // right (-hand)
if (node->left) (node->left); // unorthodox
(node); // center
(NULL);
} else {
();
node = ();
();
result.push_back(node->val);
}
}
return result;
}
};
Mid-sequence:
class Solution {
public.
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result.
stack<TreeNode*> st;
if (root ! = NULL) (root);
while (! ()) {
TreeNode* node = ();
if (node ! = NULL) {
(); // Pop the node to avoid repeating the operation and add the right-middle-left node to the stack below
if (node->right) (node->right); // add the right node (empty nodes are not added to the stack)
(node); // add middle node
(NULL); // middle node accessed but not yet processed, add empty node as marker.
if (node->left) (node->left); // add left node (empty node not on stack)
} else { // only put the next node into the result set if it encounters an empty node
(); // pop the empty node
node = (); // Retrieve the element from the stack
();
result.push_back(node->val); // add to result set
}
}
return result; }
}
};
Post-sequence:
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
if (root != NULL) (root);
while (!()) {
TreeNode* node = ();
if (node != NULL) {
();
(node); // center
(NULL);
if (node->right) (node->right); // right (-hand)
if (node->left) (node->left); // unorthodox
} else {
();
node = ();
();
result.push_back(node->val);
}
}
return result;
}
};
Unified code pattern, looks really comfortable d=====(￣▽￣*)b
hierarchical traversal
Traverse a binary tree in cascade order. That is, you traverse the binary tree one layer at a time from left to right. This traversal is not quite the same as any of the previous ones.
Need to borrow an auxiliary data structure that is the queue to achieve, the queue first-in-first-out, in line with the logic of a layer by layer traversal, while the stack first-in-first-out is suitable for simulating the depth of the priority traversal that is the logic of recursion.
And this hierarchical traversal is the breadth-first traversal in graph theory, except that we apply it to binary trees.
Upper code (●'◡'●)
Iteration:
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> que;
if (root != NULL) (root);
vector<vector<int>> result;
while (!()) {
int size = ();
vector<int> vec;
// Be sure to use a fixed size heresize，Do not use()，Because it's ever-changing.
for (int i = 0; i < size; i++) {
TreeNode* node = ();
();
vec.push_back(node->val);
if (node->left) (node->left);
if (node->right) (node->right);
}
result.push_back(vec);
}
return result;
}
};
Recursion:
class Solution {
public:
void order(TreeNode* cur, vector<vector<int>>& result, int depth)
{
if (cur == nullptr) return;
if (() == depth) result.push_back(vector<int>());
result[depth].push_back(cur->val);
order(cur->left, result, depth + 1);
order(cur->right, result, depth + 1);
}
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> result;
int depth = 0;
order(root, result, depth);
return result;
}
};
It's not easy to write a blog, so please give me some support 8~!