#include <iostream>#include <stdio.h>#include <vector>#include <string>#include <stack>#include <unordered_map>using namespace std;/*問題:Given a binary tree, return the postorder traversal of its nodes' values.For example:Given binary tree {1,#,2,3},   1    /     2    /   3return [3,2,1].Note: Recursive solution is trivial, could you do it iteratively?分析：給定一顆二叉樹，返回后續遍歷結果。后續：左右根。遞歸的寫法是:push(node->left)push(node->right)cout << node->val我們用蘸，為了能讓左孩子先出來，左孩子后壓入到棧中，每次先壓入右孩子舉例 :				1			2	       3			 4      5   6     7		   8  9       10		 11 12 11 12 8 4 9 5 2 10 6 7 3 1令當前結點為根節點，然后如果該結點有左孩子，繼續從左孩子處尋找到最左邊的孩子()找到最左邊孩子4后，4沒有左孩子，4被當做根節點，因此需要尋找4的右孩子中最左邊的孩子發現當前結點8既沒有左孩子，也沒有右孩子，此時為其父節點的右孩子，輸出：8，返回到其父節點整個的過程分為3種情況：對于當前結點，1】當前結點非空   1.1】如果當前結點有左孩子，且沒有訪問過，則壓入左孩子到棧中，并令當前結點為左孩子   1.2】否則，如果當前結點右孩子存在，且沒有訪問過，將右孩子壓入到棧中，并令當前結點為右孩子   1.3】如果當前結點沒有左孩子和右孩子，說明為葉節點，找到了，直接輸出結果，令當前結點為空2】如果當前結點為空，且棧不空，彈出棧頂元素作為當前元素輸入:61 N 2 N N 3131 2 3 4 5 6 7 N 8 9 N N 1011191 2 3 4 5 6 7 N 8 9 N N 10 N N N N 11 12輸出:3 2 18 4 9 5 2 10 6 7 3 1111 12 8 4 9 5 2 10 6 7 3 1關鍵:1 對于當前結點，1】當前結點非空   1.1】如果當前結點有左孩子，且沒有訪問過，則壓入左孩子到棧中，并令當前結點為左孩子   1.2】否則，如果當前結點右孩子存在，且沒有訪問過，將右孩子壓入到棧中，并令當前結點為右孩子   1.3】如果當前結點沒有左孩子和右孩子，說明為葉節點，找到了，直接輸出結果，令當前結點為空2】如果當前結點為空，且棧不空，彈出棧頂元素作為當前元素2另外一種解法是從前序的做法來：后序：左右根，其逆序為: 根右左，而前序為:根左右，只需要修改前序中插入左右孩子的先后順序前序：   根左右，每次將當前結點值保存，然后先壓入右孩子，再壓入左孩子后序：   左右根修改前序:根右左，再逆序為左右根。牛逼*/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> result;		if(!root)		{			return result;		}        stack<TreeNode*> nodes;		nodes.push(root);		TreeNode* node;		//原始前序：根左右，遍歷方式是：輸出當前結點元素值，插入右孩子，插入左孩子; 彈出棧頂結點		//修改前序: 根右左，先插入左孩子，再插入右孩子		while(!nodes.empty())		{			node = nodes.top();			nodes.pop();			if(node)			{				result.push_back(node->val);				nodes.push(node->left);				nodes.push(node->right);			}		}		//逆置 根右左的結果得到 左右根的后序結果		reverse(result.begin() , result.end());		return result;	}    vector<int> postorderTraversal2(TreeNode* root) {		vector<int> result;		if(!root)		{			return result;		}        stack<TreeNode*> nodes;		unordered_map<TreeNode* , bool> visited;		//nodes.push(root);		TreeNode* current = root;		while(!nodes.empty() || current)		{			//如果當前結點為空，彈出			if(current)			{				//當前結點不空，如果當前結點有左孩子，且未訪問過，壓入左孩子				if(current->left && visited.find(current->left) == visited.end())				{					nodes.push(current);					current = current->left;				}				//如果當前結點沒有左孩子或者左孩子已經訪問過，則如果其右孩子存在且未，訪問過，壓入右孩子				else if(current->right && visited.find(current->right) == visited.end())				{					nodes.push(current);					current = current->right;				}				//當前結點是葉節點，直接輸出結果，并設置當前結點為空				else				{					result.push_back(current->val);					//并設置當前結點已經訪問過					visited[current] = true;					current = NULL;				}			}			//當前結點為空，彈出棧頂結點為當前結點，繼續重復上述操作			else			{				current = nodes.top();				nodes.pop();			}		}		return result;    }};//構建二叉樹，這里默認首個元素為二叉樹根節點，然后接下來按照作為每個結點的左右孩子的順序遍歷//這里的輸入是每個結點值為字符串，如果字符串的值為NULL表示當前結點為空TreeNode* buildBinaryTree(vector<string>& nums){	if(nums.empty())	{		return NULL;	}	int size = nums.size();	int j = 0;	//結點i的孩子結點是2i,2i+1	vector<TreeNode*> nodes;	int value;	for(int i = 0 ; i < size ; i++)	{		//如果當前結點為空結點，自然其沒有左右孩子結點		if("N" == nums.at(i))		{			nodes.push_back(NULL);			continue;		}		value = atoi(nums.at(i).c_str());		TreeNode* node = new TreeNode(value);		nodes.push_back(node);	}	//設定孩子結點指向,各個結點都設置好了，如果但錢為空結點，就不進行指向	for(int i = 1 ; i <= size ; i++)	{		if(NULL == nodes.at(i-1))		{			continue;		}		if(2 * i <= size)		{			nodes.at(i-1)->left = nodes.at(2*i - 1);		}		if(2*i + 1 <= size)		{			nodes.at(i-1)->right = nodes.at(2*i);		}	}	//設定完了之后，返回根節點	return nodes.at(0);}void deleteBinaryTree(TreeNode* root){	if(!root)	{		return;	}	if(NULL == root->left && NULL == root->right)	{		delete root;		root = NULL;	}	if(root)	{		deleteBinaryTree(root->left);		deleteBinaryTree(root->right);	}}void PRint(vector<int>& result){	if(result.empty())	{		cout << "no result" << endl;		return;	}	int size = result.size();	for(int i = 0 ; i < size ; i++)	{		cout << result.at(i) << " " ;	}	cout << endl;}void process(){	 vector<string> nums;	 string value;	 int num;	 Solution solution;	 vector<int > result;	 while(cin >> num )	 {		 nums.clear();		 for(int i = 0 ; i < num ; i++)		 {			 cin >> value;			 nums.push_back(value);		 }		 TreeNode* root = buildBinaryTree(nums);		 result = solution.postorderTraversal(root);		 print(result);		 deleteBinaryTree(root);	 }}int main(int argc , char* argv[]){	process();	getchar();	return 0;}