本文主要是介绍Leetcode 145. Binary Tree Postorder Traversal二叉树后序遍历，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Given a binary tree, return the postorder traversal of its nodes' values.
Example:
Input:[1,null,2,3]1\2/3Output:[3,2,1]
题目链接:https://leetcode.com/problems/binary-tree-postorder-traversal/
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:void post_order(TreeNode* root,vector<int>&res){if(root){ post_order(root->left,res);post_order(root->right,res);res.emplace_back(root->val);}}vector<int> postorderTraversal(TreeNode* root) {vector<int> res;post_order(root,res);return res;}
};--------------------------2021年3月10日14:46:01
---------------------------2021年4月30日20:25:17
非递归算法
root是一开始就放进stack2的，所以在stk1依次放left，right，这样反过来压入stk2的时候，就是left先出，之后right出去了。这就对上后序遍历顺序了。
史上最全遍历二叉树详解 - 二叉树的前序遍历 - 力扣（LeetCode） (leetcode-cn.com)
/*** 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> res;if(!root){return res;}stack<TreeNode*> stk1;stack<TreeNode*> stk2;stk1.push(root);while(!stk1.empty()){TreeNode* node=stk1.top();stk1.pop();stk2.push(node);if(node->left){stk1.push(node->left);}if(node->right){stk1.push(node->right);}}while(!stk2.empty()){TreeNode *node=stk2.top();stk2.pop();res.push_back(node->val);}return res;}
};
这篇关于Leetcode 145. Binary Tree Postorder Traversal二叉树后序遍历的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
