Article directory
- 1. Non-recursive pre-order traversal
-
- 1.1C++ writing and analysis
- 1.2 Answer to this question ac
- 2. Non-recursive in-order traversal
- 3. Non-recursive post-order traversal
-
- 3.1 Stack simulation achieves non-recursion
-
- C++ writing method
- ac answer to this question
- Flag notation for this question
- 3.2 Reverse order thinking
- 4. Overall code
1. Non-recursive pre-order traversal
1.1C++ writing and analysis
vector<int> preorderTraversal(TreeNode* root)
{<!-- -->
vector<int> v; //v stores the data of traversed nodes
stack<TreeNode*> st; //st is a stack object. The storage data type is a pointer to a node.
TreeNode* cp = root;
while (cp || !st.empty())
{<!-- -->
//Traverse to the leftmost node
while(cp)
{<!-- -->
//Record data all the way as the traversal result
v.push_back(cp->val);
//Record pointers all the way to facilitate backtracking
st.push(cp);
cp = cp->left;
}
//The while loop ends and the leftmost node is traversed at this time
//The top node of the stack is popped and the right subtree of the top node of the stack is accessed.
TreeNode* top = st.top();
cp = top->right;
st.pop();
}
return v;
}
Ac answer to this question 1.2
void PreorderTraversal(BinTree BT)
{<!-- -->
Stack st = CreateStack();
BinTree cp = BT;
while (cp || !IsEmpty(st))
{<!-- -->
while(cp)
{<!-- -->
printf(" %c", cp->Data);
Push(st, cp);
cp = cp->Left;
}
cp = Pop(st);
cp = cp->Right;
}
}
2. Non-recursive in-order traversal
void InorderTraversal(BinTree BT)
{<!-- -->
Stack st = CreateStack();
BinTree cp = BT;
while (cp || !IsEmpty(st))
{<!-- -->
//Traverse to the leftmost node
while(cp)
{<!-- -->
//Record pointers all the way to facilitate backtracking
Push(st, cp);
cp = cp->Left;
}
//The leftmost node has been reached at this time
//Assume that the most recently traversed node is x
//Pop x from the stack and record the x pointer
// 1. Pop x from the stack: x has been traversed in the correct order and is useless
// 2. Record the x pointer: access x data and access the right subtree of x
//Pop the stack record pointer
cp = Pop(st);
//Access data
printf(" %c", cp->Data);
//Access the right subtree
cp = cp->Right;
//The right empty stack is not empty and there are still nodes to be traversed. Execute the next big while loop.
//The right empty stack is empty and the traversal ends
}
}
3. Non-recursive post-order traversal
3.1 Stack simulation implements non-recursion
C++ writing
vector<int> postorderTraversal(TreeNode* root)
{<!-- -->
vector<int> v;
stack<TreeNode*> st;
TreeNode* cp = root;
TreeNode* prv = nullptr;
while (cp || !st.empty())
{<!-- -->
//Traverse all the way and record the pointer to the leftmost node
while(cp)
{<!-- -->
st.push(cp);
cp = cp->left;
}
//The end of the while loop has reached the leftmost node cp points to the left child of the leftmost node (null)
Determine and process the top node of the stack
TreeNode* top = st.top();
//The left is already empty. If the right is also empty, the left and right traversals have ended and the root needs to be accessed.
if (top->right == nullptr || top->right == prv)
{<!-- -->
//Record the currently visited node
prv = top;
//Access data
v.push_back(top->val);
//pop
st.pop();
}
else
cp = top->right;
//cp still points to the left child of the node (null)
}
return v;
};
Ac answer to this question
void PostorderTraversal(BinTree BT)
{<!-- -->
Stack st = CreateStack();
BinTree cp = BT;
BinTree prv = NULL;
while (cp || !IsEmpty(st))
{<!-- -->
while(cp)
{<!-- -->
Push(st, cp);
cp = cp->Left;
}
BinTree top = Peek(st);
if (top->Right == NULL || top->Right == prv)
{<!-- -->
prv = top;
printf(" %c", top->Data);
Pop(st);
}
else
cp = top->Right;
}
}
Flag notation for this question
void PostorderTraversal(BinTree BT)
{<!-- -->
if (BT == NULL)
return;
Stack st = CreateStack();
BinTree cp = BT;
cp->flag = 0;
while (cp || !IsEmpty(st))
{<!-- -->
//Traverse all the way and record the pointer to the leftmost node
while(cp)
{<!-- -->
Push(st, cp);
cp->flag + + ;//Indicates that the left subtree has been traversed
cp = cp->Left;
}
cp = Peek(st);
if (cp->flag == 2) //Both the left and right subtrees are traversed
{<!-- -->
//access
printf(" %c", cp->Data);
//pop
Pop(st);
//A stroke of genius:
// Setting cp empty indicates that the current subtree has been visited
// Need to access the next top of the stack, that is, the previous node
cp = NULL;
}
else
{<!-- -->
cp->flag + + ;
cp = cp->Right;
}
}
}
3.2 Reverse order thinking
Preorder traversal order: root left right
Postorder traversal order: left right root
For forward thinking, we saw in 2.1 above that there are two methods to determine whether the right subtree has been traversed:
- Add a flag status mark to the node class in the binary tree. If the left and right subtrees of a node have been accessed, flag == 2 (in fact, this method is not recommended because the effective data of the binary tree should be the data field + pointer field directly Adding a flag to a binary tree is really harmful)
- Create a prv pointer pointing to the last visited top. The next time the right subtree is accessed, determine whether it has been accessed.
What does reverse order thinking look like?
If we can traverse in the order of root, right, left and finally in reverse order, we can successfully complete the post-order traversal.
Why does reverse-order thinking not require judgment of special situations? For example, setting a flag or making a prv?
Thinking in reverse order: The root is pushed into the stack first to access the root. The root is popped out of the stack and the left and right subtrees are pushed into the stack in sequence. At this time, the order of nodes stored in the stack is: Left child, right child Because the stack comes first The feature stack that comes out later can first access its right child, the right child is pushed onto the stack, and the right child’s left and right subtrees are pushed onto the stack…
Some students may ask why not just forward the order directly? For example: the root is not pushed onto the stack first, but the right subtree and left subtree are pushed onto the stack in order. Doesn’t this allow forward output?
Students who have such a problem have obviously ignored the triggering conditions for reverse order thinking: the stack is not empty. Perform reverse order operations under the condition that the stack is not empty. If the forward operation is performed when both the left and right subtrees have been visited, there is no way to access the root at the end, but reverse order thinking can. Access the root at the beginning and reverse the data accessed at the end.
class Solution
{<!-- -->
public:
vector<int> postorderTraversal(TreeNode* root)
{<!-- -->
vector<int> v;
stack<TreeNode*> st;
//For each node:
// Push into the stack - top points to the node - pop out of the stack - 1. top is not empty - access the data and push its left and right children onto the stack
// 2. Top is empty--no need to access data, no need to push its left and right sub-folders onto the stack
st.push(root);
while (!st.empty())
{<!-- -->
TreeNode* top = st.top();
st.pop();
if (top != nullptr)
v.push_back(top->val);
else
continue;
st.push(top->left);
st.push(top->right);
}
reverse(v.begin(), v.end());
return v;
}
};
4. Overall code
void InorderTraversal(BinTree BT)
{
Stack st = CreateStack();
BinTree cp = BT;
while (cp || !IsEmpty(st))
{
while(cp)
{
Push(st, cp);
cp = cp->Left;
}
cp = Pop(st);
printf(" %c", cp->Data);
cp = cp->Right;
}
}
void PreorderTraversal(BinTree BT)
{<!-- -->
Stack st = CreateStack();
BinTree cp = BT;
while (cp || !IsEmpty(st))
{<!-- -->
while(cp)
{<!-- -->
printf(" %c", cp->Data);
Push(st, cp);
cp = cp->Left;
}
cp = Pop(st);
cp = cp->Right;
}
}
void PostorderTraversal(BinTree BT)
{<!-- -->
Stack st = CreateStack();
BinTree cp = BT;
BinTree prv = NULL;
while (cp || !IsEmpty(st))
{<!-- -->
while(cp)
{<!-- -->
Push(st, cp);
cp = cp->Left;
}
BinTree top = Peek(st);
if (top->Right == NULL || top->Right == prv)
{<!-- -->
prv = top;
printf(" %c", top->Data);
Pop(st);
}
else
cp = top->Right;
}
}