当前位置:网站首页>LeetCode145. Post order traversal of binary tree (three methods of recursion and iteration)
LeetCode145. Post order traversal of binary tree (three methods of recursion and iteration)
2022-07-05 22:54:00 【Qingshan's green shirt】
LeetCode145. Postorder traversal of binary trees
List of articles
1. problem
2. Ideas
(1) What is post order traversal
(2) recursive
It's the same as the previous sequence and the middle sequence , Just put the root node to the last access
(3) Iterative thinking
a. Transform preorder traversal
b. Fake middle root traversal
Middle root traversal :1. From the root node From top to bottom Go down the left branch , And put the nodes along the way Pressing stack , Until the deepest node ( No left child ).
2. Follow the left passage , Play the stack from bottom to top , Sequential access All nodes along the way And its Right subtree .
As shown in the figure below :
The post order traversal faces a problem : Behind the bomb stack , Cannot access immediately p, But first visit p The right subtree , And then visit p. So it needs to be preserved in some way p.
Strategy 1: Don't talk about stack p, Instead, only take the value of the element at the top of the stack .
Strategy 2: Allow nodes to enter and leave the stack multiple times , Instant bomb stack p Then let it enter the stack immediately .
Strategy 1
Strategy 2:
Set a binary in the stack element , Maintain a label i,i Represents the current node / Stack times . Any node in a binary tree p You have to enter the stack three times , Out of stack three times .
The first time out of the stack is for traversal p The left subtree .
The second battle is for traversal p The right subtree .
The third time is to access p.
Operation example
Pseudo code
3. Code implementation
(1) recursive
class Solution
{
public:
void posOrder(TreeNode*cur,vector<int>& vec)
{
if(cur == NULL)return;
posOrder(cur->left,vec);// Left
posOrder(cur->right,vec);// Right
vec.push_back(cur->val);// root
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
posOrder(root, result);
return result;
}
};
(2) iteration
a. Transform preorder traversal
class Slution{
public:
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*>st;
vector<int> result;
if(root == NULL) return result;
st.push(root);
while(!st.empty()){
TreeNode* node = st.pop();
st.pop();
result.push_nack(node->val);
if(node->left st.push(node->left));// Relative to the previous sequence traversal, make a change here
if(node->right) st.push(node->right);// Empty nodes do not stack
}
reverse(result.begin(),result.end());// The reverse result is the order of left and right
return result;
}
};
b. Strategy 1
class Solution{
public:
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*>st;
vector<int> result;
TreeNode* p = root;
TreeNode* pre = NULL;// pre yes p After the root of the precursor , That is to say p Previously visited nodes
while(1){
while(p!=NULL){
st.push(p);
p = p->left;
}
if(st.empty()) return result;
p = st.top();
if(p!=NULL){
if( p->right == NULL||pre == p->right)
{
p = st.top();st.pop();
result.push_back(p->val);
pre = p; p = NULL;
}
else p = p->right;
}
}
}
};
b. Strategy 2
Use STL:
class Solution{
public:
vector<int> postorderTraversal(TreeNode* root) {
int flag[512];
int top = 0;//top Point to the position where the element will be placed It really doesn't work because stl There is no change in top
stack<TreeNode*>st;
vector<int> result;
flag[top] = 1;
st.push(root);
top++;
while(!st.empty()){
TreeNode* p = st.top();
st.pop();// Out of the stack
top--;
if(flag[top] == 1){
flag[top] = 2; st.push(p); top++;
if(p!= NULL && p->left != NULL)
{
flag[top] = 1;
st.push(p->left);
top++;
}
}
else if(flag[top] == 2)
{
flag[top] = 3; st.push(p);top++;
if(p!=NULL && p->right != NULL){
flag[top] = 1;
st.push(p->right);
top++;
}
}
else if(p!=NULL && flag[top] == 3)
result.push_back(p->val);
}
return result;
}
};
Be careful !top It needs to be maintained additionally !stl There's no such thing as int top This kind of thing !
Don't use STL:
int flag[512];
int top = 0;//top Point to the position where the element will be placed
class stac{
public:
void InitStack(){
top = 0;
}
void Push(TreeNode *p){
stack[top++] = p;
}
TreeNode* Pop(){
top--;
return stack[top];
}
bool empty() {
if (top == 0)return true;
return false;
}
TreeNode* Top( ){
return stack[top-1];
}
private:
TreeNode *stack[512];
};
class Solution{
public:
vector<int> postorderTraversal(TreeNode* root) {
stac st;
st.InitStack();
vector<int> result;
flag[top] = 1;
st.Push(root);
while(!st.empty()){
TreeNode* p = st.Pop();// Out of the stack
if(flag[top] == 1){
flag[top] = 2; st.Push(p);
if(p!= NULL && p->left != NULL)
{
flag[top] = 1;
st.Push(p->left);
}
}
else if(flag[top] == 2)
{
flag[top] = 3; st.Push(p);
if(p!=NULL && p->right != NULL){
flag[top] = 1;
st.Push(p->right);
}
}
else if(p!=NULL && flag[top] == 3)
{
result.push_back(p->val);
}
else
continue;
}
return result;
}
};
边栏推荐
- [speech processing] speech signal denoising based on Matlab GUI Hanning window fir notch filter [including Matlab source code 1711]
- Hcip day 12 (BGP black hole, anti ring, configuration)
- Binary tree (III) -- heap sort optimization, top k problem
- APK加固技术的演变,APK加固技术和不足之处
- Metasploit(msf)利用ms17_010(永恒之蓝)出现Encoding::UndefinedConversionError问题
- Business introduction of Zhengda international futures company
- Nacos installation and service registration
- a-tree 树的全部展开和收起
- opencv 判断点在多边形内外
- 终于搞懂什么是动态规划的
猜你喜欢
随机推荐
基于STM32的ADC采样序列频谱分析
Navigation day answer applet: preliminary competition of navigation knowledge competition
Double pointeur de liste liée (pointeur rapide et lent, pointeur séquentiel, pointeur de tête et de queue)
Solve the problem of "no input file specified" when ThinkPHP starts
fibonacci search
查看网页最后修改时间方法以及原理简介
Go language learning tutorial (XV)
抖音__ac_signature
Starting from 1.5, build a micro Service Framework -- log tracking traceid
The introduction to go language is very simple: String
透彻理解JVM类加载子系统
Binary tree (III) -- heap sort optimization, top k problem
MCU case -int0 and INT1 interrupt count
Postman核心功能解析-参数化和测试报告
First, redis summarizes the installation types
Evolution of APK reinforcement technology, APK reinforcement technology and shortcomings
航海日答题小程序之航海知识竞赛初赛
MoCo: Momentum Contrast for Unsupervised Visual Representation Learning
Metasploit (MSF) uses MS17_ 010 (eternal blue) encoding:: undefined conversionerror problem
Global and Chinese markets for children's amusement facilities 2022-2028: Research Report on technology, participants, trends, market size and share