Given a binary tree, return the postorder traversal of its nodes' values.
For example:
Given binary tree{1,#,2,3},
1
\
2
/
3
return[3,2,1].
Note: Recursive solution is trivial, could you do it iteratively?
后序遍历：左孩子->右孩子->根节点
后序遍历最关键的是利用一个指针保存前一个访问过的信息，避免重复访问。
思路一：
左、右孩子是交叉入栈的，当出栈时，就存在如何从左孩子转向右孩子同时避免重复访问的问题。一个节点值被取出来时，它的左右子节点要么不存在，要么已经被访问过。所以，用head来保存上一个已访问元素的信息，然后判断是否为栈顶元素的左右孩子来实现避免重复访问，至于从左转向右，入栈的顺序已经解决这个问题。原代码
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> postorderTraversal(TreeNode *root)
{
vector<int> res;
stack<TreeNode *>stk;
if(root) stk.push(root);
TreeNode *head=root;
while( !stk.empty())
{
TreeNode *top=stk.top();
if(( !top->left&& !top->right)||top->left==head||top->right==head)
{ //两种情况：一、到达叶节点；二、前一元素是栈顶的左、右孩子即被访问过
res.push_back(top->val);
stk.pop();
head=top;
}
else //结合栈的特点和后边遍历的顺序，右先进
{
if(top->right)
stk.push(top->right);
if(top->left)
stk.push(top->left);
}
}
return res;
}
};
思路二：
【后序遍历二叉树的步骤：先遍历二叉树的左子树，再遍历二叉树的右子树，最后访问根结点。非递归实现时，用一个栈模拟遍历过程。由于访问完左子树后访问右子树，栈中元素要起到转向访问其右子树的作用，但是不能像先序和中序遍历那样出栈即可，因为根结点时最后访问的。那么什么时候出栈呢？我们需要一个指针pre来记录前一次访问的结点。如果pre是根结点的右子树，则说明根结点的右子树访问完了，此时根结点就可以出栈了(源代码）】。过程：将左孩子不停的压入栈中，直到由root=root->left得到root为空，然后将栈顶元素的值存入res，用pre记录栈顶元素（在后来可以避免重复访问）。在下次循环中，因，root为空，所以跳过if进入判断else if实现左孩子向右孩子的转变。整体上，左孩子出栈以后，右孩子入栈，用pre记录右孩子，右孩子出栈，利用stk.top()->right !=pre来避免重复访问。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> postorderTraversal(TreeNode *root)
{
vector<int> res;
stack<TreeNode *> stk; TreeNode *pre=NULL;
while(root|| !stk.empty())
{
if(root)
{
stk.push(root);
root=root->left;
}
else if(stk.top()->right !=pre) //判断stk.top()->right是否被访问过
{
root=stk.top()->right;
pre=NULL;
}
else
{
res.push_back(stk.top()->val);
pre=stk.top();
stk.pop();
}
}
return res; }
};
思路三：递归版
class Solution {
public:
vector<int> postorderTraversal(TreeNode *root)
{
vector<int> res;
postOrderTrav(root,res);
return res;
}
void postOrderTrav(TreeNode *root,vector<int> &res)
{
if(root==NULL) return;
postOrderTrav(root->left,res);
postOrderTrav(root->right,res);
res.push_back(root->val);
}
};