1. 题意

求后序遍历

2. 题解

2.1 递归

class Solution {
public:void addPost(TreeNode *root, vector<int> &res) {if ( nullptr == root)return ;addPost(root->left, res);addPost(root->right, res);res.emplace_back( root->val );}vector<int> postorderTraversal(TreeNode *root) {vector<int> res;addPost(root, res);return res;}
};

2.2 迭代

class Solution {
public:vector<int> postorderTraversal(TreeNode *root) {vector<int> res;stack<TreeNode *> s;TreeNode *pre = nullptr;while ( root || !s.empty()) {// 递归遍历左子树if ( root ) {s.push(root);root = root->left;continue;}// 如果根节点没有右子树或者右子树已经访问过// 则将该节点的值放入答案// 将上一个访问完成的子树设置为当前值// 将当前访问的子树置为空// 弹出当前访问的子树(root)// 否则遍历右子树if (!s.empty()) {root = s.top();if (root->right == nullptr || root->right == pre ) {res.emplace_back(root->val);pre = root;root = nullptr;s.pop();}else {root = root->right;}}}return res;}
};