写法一(递归写法)
/**
* 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> res;
void dfs(TreeNode* root)
{
if(!root) return;
if(root->left) dfs(root->left);
if(root->right) dfs(root->right);
res.push_back(root->val);
}
vector<int> postorderTraversal(TreeNode* root) {
dfs(root);
return res;
}
};
写法二(巧解)
对前序遍历的迭代写法略作修改,使其按“根右左”的顺序遍历,然后将得到的序列翻转即为后序遍历
/**
* 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;
stack<TreeNode*> stk;
while(root || stk.size())
{
while(root)
{
res.push_back(root->val);
stk.push(root);
root = root->right; //这里是从前序遍历的root=root->left修改为right
}
root = stk.top()->left; // 从前序遍历的right修改为left
stk.pop();
}
reverse(res.begin(), res.end()); //翻转得到的“根右左”序列得到“左右根”序列
return res;
}
};
写法三(通解)
正常的后序遍历迭代写法(不借助其他标记)
/**
* 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;
stack<TreeNode*> stk;
while(root || stk.size()) // while 跳过初始时x==NULL的情况
{
if(root->left)
{
stk.push(root);
root = root->left;
}
else if(root->right)
{
stk.push(root);
root = root->right;
}
else // 当前结点没有孩子
{
res.push_back(root->val); // 访问当前结点
while(stk.size())
{
auto t = stk.top(); // 当前栈顶结点必然是当前结点的父结点
if(t->left == root && t->right) // 如果当前结点是左孩子,且父结点有右孩子
{
root = t->right; // 则转向右孩子,不pop父结点
break;
}
else
{
stk.pop(); // 否则pop并访问该父结点(此时孩子已经全部访问完)
root = t; // 循环直到栈空或父结点有右孩子
res.push_back(root->val);
}
}
}
if(stk.empty()) break; // 如果栈空了,说明根节点已被访问,遍历完成
}
return res;
}
};
写法四 (巧解)
参考题解:LeetCode 145. 二叉树的后序遍历
在栈中加入一个空节点作为标记,当弹出空节点时说明左右子树已经遍历完了,此时访问当前节点。如果弹出的节点不空,那就按照右子树、左子树的顺序入栈(因为这样最后出来的顺序才是左右根)
/**
* 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;
stack<TreeNode*> stk;
if (root) stk.push(root); // root非空,则入栈
while (stk.size())
{
auto t = stk.top(); // 先取出栈顶元素
stk.pop();
// 如果非空,说明当前结点没有被访问过(访问过的节点其上面有空节点先被弹出来)
if (t)
{
stk.push(t); // 那么我们把当前节点入栈
stk.push(NULL); // 然后再加一个空节点作为标记,表示已经访问过了
// 先放右子树,再放左子树,这样出栈的时候就是左右根(根节点最先入栈最后出)
if (t->right) stk.push(t->right);
if (t->left) stk.push(t->left);
}
else // 是空节点,那么说明其下一个节点就是答案数组中的元素
{
t = stk.top(); // 取出答案元素
stk.pop(); // 弹栈
res.push_back(t->val); // 将答案元素的值加入result数组
}
}
return res;
}
};