Leetcode 之Binary Tree Postorder Traversal（44）

后序遍历，比先序和中序都要复杂。访问一个结点前，需要先判断其右孩子是否被访问过。如果是，则可以访问该结点；否则，需要先处理右子树。

 vector<int> postorderTraversal(TreeNode *root){vector<int> result;stack<TreeNode *>s;TreeNode *p, *q;//一个表示当前访问的结点，一个表示刚刚访问过的结点p = root;do{while (p != nullptr){//不断将左结点压入
                  s.push(p);p = p->left;}q = nullptr;//压到底时，刚刚访问过的结点必定为空结点while (!s.empty()){p = s.top();s.pop();if (p->right == q){//如果当前结点的右结点已经被访问,则访问该结点result.push_back(p->val);q = p;}else{//右孩子没有被访问过，则继续压入,先处理右子树
                      s.push(p);p = p->right;break;}}} while (!s.empty());}