leecode 解题总结：145. Binary Tree Postorder Traversal

#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;}