Leetcode 145. Binary Tree Postorder Traversal二叉树后序遍历

本文主要是介绍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二叉树后序遍历的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---