当前位置:网站首页>Write down the post order traversal of the ~ binary tree
Write down the post order traversal of the ~ binary tree
2022-04-23 09:01:00 【Xiaoqiang~】
Writing to remember ~ Postorder traversal of binary trees
0、 Preface
This blog is to buckle 145. Postorder traversal of binary trees Problem solving , The title is simple. , Blogging is mainly because it can also be used as DFS Examples ~
Preorder traversal of binary tree Click here to To view the !
The middle order traversal of binary tree can Click here to To view the !
1、 Title Description
2、 Their thinking
2.1 Method 1 ~ recursive
2.1.1 Ideas
The post order traversal of binary tree is based on the access The left subtree – Right subtree – The root node Traverse the target tree in a way , When accessing the left subtree or right subtree, you can traverse in the same way , Until you walk through the whole tree . In combination with this approach, recursion can be used directly !
2.1.2 Program code
/** * 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:
void postorder(TreeNode* root, vector<int>& ans)
{
if(!root)
return;
postorder(root->left,ans);
postorder(root->right,ans);
ans.push_back(root->val);
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ans;
postorder(root,ans);
return ans;
}
};
2.2 Method 2 ~ DFS
2.2.1 Ideas
What about this idea , Is based on the force given on the buckle DFS Templates 2 Written by . Although it feels more like iteration , harm !
The idea here is equivalent to the method 1 The train of thought unfolds , From implicit stack to explicit stack , Everything else is the same , The specific implementation can be seen in the following code . But when expanding here, you need to judge the right subtree ! See the following procedure for details
2.2.2 Program code
/** * 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) {
vector<int> ans;
stack<TreeNode*> st;
TreeNode* cur = root;
TreeNode* prev;
while(cur || !st.empty())
{
while(cur)
{
st.push(cur);
cur = cur->left;
}
TreeNode* top = st.top();
if(top->right == nullptr || top->right == prev)
{
ans.push_back(top->val);
st.pop();
prev = top;
}
else
cur = top->right;
}
return ans;
}
};
版权声明
本文为[Xiaoqiang~]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/04/202204230726592713.html
边栏推荐
- 错误: 找不到或无法加载主类
- What is augmented reality technology? Where can it be used?
- 企业微信应用授权/静默登录
- I don't understand time, timestamp and time zone. Look at this article
- Virtual online exhibition - Online VR exhibition hall realizes 24h immersive exhibition viewing
- Technological innovation in government affairs in the construction of Digital Government
- L2-022 重排链表 (25 分)(map+结构体模拟)
- Illegal character in scheme name at index 0:
- LaTeX论文排版操作
- Learn SQL injection in sqli liabs (Level 11 ~ level 20)
猜你喜欢
Cadence process angle simulation, Monte Carlo simulation, PSRR
PCTP考试经验分享
调包求得每个样本的k个邻居
L2-3 romantic silhouette (25 points)
L2-024 tribe (25 points) (and check the collection)
汇编语言与逆向工程 栈溢出漏洞逆向分析实验报告
2021 Li Hongyi's adaptive learning rate of machine learning
LLVM之父Chris Lattner:编译器的黄金时代
First principle mind map
GUI编程简介 swing
随机推荐
Arbre de dépendance de l'emballage des ressources
微信:获取单个标签所有人
Go language self-study series | golang nested structure
Go语言自学系列 | golang方法
Restore binary tree (25 points)
The crawler returns null when parsing with XPath. The reason why the crawler cannot get the corresponding element and the solution
玩转二叉树 (25 分)
valgrind和kcachegrind使用運行分析
汇编语言与逆向工程 栈溢出漏洞逆向分析实验报告
L2-024 部落 (25 分)(并查集)
L2-022 rearrange linked list (25 points) (map + structure simulation)
Cadence process angle simulation, Monte Carlo simulation, PSRR
Latex mathematical formula
Brush classic topics
Single chip microcomputer nixie tube stopwatch
Bk3633 specification
OneFlow学习笔记:从Functor到OpExprInterpreter
计算神经网络推理时间的正确方法
Flink reads MySQL and PgSQL at the same time, and the program will get stuck without logs
Four pictures to understand some basic usage of Matplotlib