LeetCode | Binary Tree Postorder Traversal

本文主要是介绍LeetCode | Binary Tree Postorder Traversal，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

后序遍历，当然，，，用栈实现

后序遍历的关键在于从左孩子回到根节点和从右孩子回到跟节点。
如果是从左回的，要继续向右。如果是从右边回来的（表明左右孩子已经遍历结束）这时候就需要将自身输出。

具体到代码上，就是使用一个q指针，用于保存上一个走过的节点（确切的说应该是输出的节点）。
然后从栈顶取出元素的时候，判断p->right==q? 来决定它是从哪个方向回来的~
完成使命~~

注释里面也说的比较清楚~

class Solution{
public:vector<int> postOrder(TreeNode* root){vector<int> result;if(!root) return result;stack<TreeNode*> Q;//p正在访问的节点  q刚刚访问过的节点TreeNode* p=root,*q=NULL;do{while(p){Q.push(p);p=p->left;}q=NULL;while(!Q.empty()){p=Q.top();Q.pop();//后序遍历是先访问左、右子树,再访问根节点，而在非递归算法中，//利用栈回退到时，并不知道是从左子树回退到根节点，//还是从右子树回退到根节点，//如果从左子树回退到根节点，此时就应该去访问右子树，//而如果从右子树回退到根节点，此时就应该访问根节点。//所以相比前序和后序，必须得在压栈时添加信息，//以便在退栈时可以知道是从左子树返回，还是从右子树返回进而决定下一步的操作。//对应到这里，就是使用历史访问节点q//这里相等表示访问了右边节点返回的 if(p->right==q) {result.push_back(p->val);q=p;//保存刚刚访问过的节点 }else{//当前节点不能访问，需要再次入栈//因为检测到当前节点是从左孩子回溯回来的//所以首先要将当前压栈操作 Q.push(p);p=p->right;break;}}}while(!Q.empty());return result;}
};