Table of Contents
?edit
1. Preorder traversal
Question interface:
Recursive solution:
Non-recursive solution:
2. In-order traversal
Question interface:
Recursive solution:
Non-recursive writing:
3. Post-order traversal
Question interface:
Recursive solution:
Non-recursive solution:
One, preorder traversal
Question interface:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
*TreeNode *left;
*TreeNode *right;
* TreeNode(): val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
}
};
Recursive solution:
I believe everyone can solve this problem easily. Recursive writing is very simple:
class Solution {
public:
void _preorderTraversal(TreeNode*root, vector<int> & amp;ret)
{
if(root == nullptr)
{
return ;
}
ret.push_back(root->val);
_preorderTraversal(root->left, ret);
_preorderTraversal(root->right,ret);
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int>ret;
_preorderTraversal(root,ret);
return ret;
}
};
Non-recursive solution:
But what if you were asked to write a non-recursive version? How should we write it? Proceed as follows:
1. Create a stack. The function of this stack is to store each node.
2. Define a cur pointer pointing to the current node. Then starting from the node cur, use a small loop to traverse the left subtree. After traversing a left subtree, that is, after traversing to nullptr, the loop ends.
3. Get the top element top from the stack and let cur point to the right pointer of top again. Then re-traverse the left subtree starting from the new cur.
4. When the stack is empty and cur is nullptr, you can end the large loop and return the result of the pre-order traversal.
code show as below:
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int>ret;//array to store results
stack<TreeNode*>st;//stack
TreeNode*cur = root;
while(!st.empty()||cur)//Loop end condition, the loop must be ended when both are nullptr.
{
while(cur)
{
ret.push_back(cur->val);
st.push(cur);
cur = cur->left;
}
TreeNode* top = st.top();
st.pop();
cur = top->right;//Point to the right node and traverse the right tree.
}
return ret;
}
};
To summarize, the key step here is to traverse the left tree of each node. Then record each node using the stack. Why use the stack here? This takes advantage of the last-in-first-out feature of the stack! ! ! Since drawing on a computer is troublesome, you can draw and simulate it yourself based on this code.
Two, mid-order traversal
Question interface:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
*TreeNode *left;
*TreeNode *right;
* TreeNode(): val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
}
};
Recursive solution:
It is still simple to use the recursive solution, that is, recursively traverse the binary tree in the order of left subtree -> root -> right subtree. code show as below:
class Solution {
public:
void _inorderTraversal(TreeNode*root, vector<int> & amp;in)
{
if(root == nullptr)
{
return;
}
_inorderTraversal(root->left,in);
in.push_back(root->val);
_inorderTraversal(root->right,in);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int>in;
_inorderTraversal(root,in);
return in;
}
};
Non-recursive writing:
With the above idea of non-recursive writing of pre-order traversal, it is much easier to write non-recursive writing of in-order traversal. We only need to change the order in which the root nodes are inserted into the in array in the non-recursive writing of preorder traversal. code show as below:
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int>ret;//array to store results
stack<TreeNode*>st;//stack
TreeNode*cur = root;
while(!st.empty()||cur)//Loop end condition, the loop must be ended when both are nullptr.
{
while(cur)//This loop only inserts the pointer of the inserted node into the stack st and does not insert the value into ret.
{
st.push(cur);
cur = cur->left;
}
TreeNode* top = st.top();
ret.push_back(top->val); //Insert value here
st.pop();
cur = top->right;//Point to the right node and traverse the right tree.
}
return ret;
}
};
Three, post-order traversal
Question interface:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
*TreeNode *left;
*TreeNode *right;
* TreeNode(): val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
}
};
Recursive solution:
The recursive solution to this problem is still very simple, which is to traverse the binary tree in the order of left subtree -> right subtree -> root. The recursive code is as follows:
class Solution {
public:
void _postorderTraversal(TreeNode*root,vector<int> & amp;ret)
{
if(root == nullptr)
{
return;
}
_postorderTraversal(root->left,ret);
_postorderTraversal(root->right,ret);
ret.push_back(root->val);
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int>ret;
_postorderTraversal(root,ret);
return ret;
}
};
Non-recursive solution:
The difficulty of this problem is how should we write the code for the non-recursive solution? This is where the difficulty lies. First of all, we all know that the traversal order of post-order distribution traversal is: left subtree -> right subtree -> root. So we still have to visit the left subtree first. We still have to access the left first and insert all left nodes into the stack first. This step is actually the same as the previous in-order traversal and pre-order traversal. However, in post-order traversal, whether the current node can be accessed needs to be judged: The current node can only be accessed after the right node is accessed. .
code show as below:
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*>st;
vector<int>ret;
TreeNode*cur = root;
TreeNode*prev = nullptr;//Record which node was visited previously
while(!st.empty()||cur)
{
while(cur)//Only insert and not access
{
st.push(cur);
cur = cur->left;
}
TreeNode* top = st.top();//Find the last node inserted into the stack
if(prev == top->right)//If the right node of this node has been visited, this node is accessible
{
prev = top;//update prev
ret.push_back(top->val);
st.pop();
}
else//If the right node of this node has not been visited, visit the right node (right tree) first
{
cur = top->right;
prev = cur;//update prev
}
}
return ret;
}
};