学步园

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].

	vector<int> postorderTraversal1(TreeNode *root){ //非递归的方法
		vector<int> v;
		stack<const TreeNode *> s;
		/* p，正在访问的结点， q，刚刚访问过的结点 */
		const TreeNode *p,*q;
		p = root;

<span style="white-space:pre">		</span>do 
		{
			while(p != nullptr){//往左下方走
				s.push(p);
				p = p->left;
			}
			while(!s.empty())
			{
				p = s.top();
				s.pop();

				if(p->right == q || p->right == nullptr) //右孩子不存在或已访问
				{
					v.push_back(p->val);
					q = p; //保存刚刚访问的节点
				}
				else
				{
					s.push(p);//右节点不为空，需二次访问
					p = p->right;
					break;
				}
			}
		} 
		while (!s.empty());

<span style="white-space:pre">		</span>return v; 
	}