题目链接
https://leetcode-cn.com/problems/binary-tree-postorder-traversal/description/
题解一:递归
// Problem: LeetCode 145
// URL: https://leetcode-cn.com/problems/binary-tree-postorder-traversal/description/
// Tags: Stack Tree Recursion
// Difficulty: Hard
#include <iostream>
#include <vector>
using namespace std;
struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x): val(x), left(nullptr), right(nullptr){}
};
class Solution{
public:
vector<int> result;
void traversal(TreeNode* root){
if(root!=nullptr){
if(root->left!=nullptr)
traversal(root->left);
if(root->right!=nullptr)
traversal(root->right);
result.push_back(root->val);
}
}
vector<int> postorderTraversal(TreeNode* root){
traversal(root);
return result;
}
};
int main()
{
cout << "helloworld" << endl;
// system("pause");
return 0;
}
题解二:非递归(通过栈模拟递归)
思路:https://www.cnblogs.com/chouxianyu/p/13293284.html
// Problem: LeetCode 145
// URL: https://leetcode-cn.com/problems/binary-tree-postorder-traversal/description/
// Tags: Stack Tree Recursion
// Difficulty: Hard
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x): val(x), left(nullptr), right(nullptr){}
};
class Solution{
public:
vector<int> postorderTraversal(TreeNode* root){
vector<int> result;
stack<TreeNode*> nodes;
if(root!=nullptr)
nodes.push(root);
while(!nodes.empty()){
root = nodes.top();
nodes.pop();
// 模拟调用递归函数
if(root!=nullptr){
nodes.push(root);
nodes.push(nullptr);
if(root->right!=nullptr)
nodes.push(root->right);
if(root->left!=nullptr)
nodes.push(root->left);
}
// 递归函数调用成功
else{
result.push_back(nodes.top()->val);
nodes.pop();
}
}
return result;
}
};
int main()
{
cout << "helloworld" << endl;
// system("pause");
return 0;
}
作者:@臭咸鱼
转载请注明出处:https://www.cnblogs.com/chouxianyu/
欢迎讨论和交流!