刷题——二叉树的后续遍历

方法一：双指针法

 void  postorder(TreeNode* root, vector<int>&res){if(root == NULL) return;postorder(root->left,res);postorder(root->right,res);res.push_back(root->val);}vector<int> postorderTraversal(TreeNode* root) {// write code herevector<int>res;postorder(root, res);return res;}

方法二：入栈出栈法

vector<int> postorderTraversal(TreeNode* root) {vector<int> res;stack<TreeNode*> s;TreeNode* prev = nullptr; // 用于跟踪上一个访问的节点while (root != nullptr || !s.empty()) {while (root != nullptr) {s.push(root);root = root->left; // 先尽可能遍历到最左边}root = s.top(); // 获取当前栈顶元素（最深的未完全访问的节点）// 检查是否可以访问当前节点（即其右子树已访问或无右子树）if (root->right == nullptr || root->right == prev) {res.push_back(root->val); // 访问当前节点prev = root; // 更新prev为当前节点，表示其左右子树均已处理s.pop(); // 弹出当前节点，准备处理下一个root = nullptr; // 重置root，将在下次循环中从栈中获取新的节点} else {// 如果当前节点的右子树还未访问，则转向访问右子树root = root->right;}}return res;
}