leecode 解题总结：144. Binary Tree Preorder Traversal

#include <iostream>#include <stdio.h>#include <vector>#include <string>#include <unordered_map>#include <stack>using namespace std;/*问题:Given a binary tree, return the PReorder traversal of its nodes' values.For example:Given binary tree {1,#,2,3},   1    /     2    /   3return [1,2,3].Note: Recursive solution is trivial, could you do it iteratively?分析:二叉树前序遍历的非递归算法。也需要用一个栈来做。前序遍历:根左右，当前遍历的结点直接存储结果集。在寻找最左边结点的时候，将沿途访问的结点压入栈，将结点的值压入结果集，并设置访问标记但是寻找的时候是先寻找最左边结点，直到当前结点找不到最左边结点，然后弹出栈顶结点（也就是最左边结点），然后令该结点的右结点成为当前结点，重复上述过程举例 :				1			2	       3			 4      5   6     7		   8  9       10		              输入:61 N 2 N N 3131 2 3 4 5 6 7 N 8 9 N N 1011输出:1 2 31 2 4 8 5 9 3 6 10 71关键:1 采用一个栈，根据前序：根左右的方式，因为每次弹出的结点为根节点，下面就是要把左和右的结点压入栈中。具体由于我们要先访问左孩子，因此栈中先压入当前访问结点的右孩子，再压入左孩子即可。左右->栈先压入右孩子，再压入左孩子2 采用栈+中序遍历+哈希map设定访问标记的方式来做，已经放过的结点的值不存储到结果集中*/struct TreeNode {    int val;	TreeNode *left;	TreeNode *right;	TreeNode(int x) : val(x), left(NULL), right(NULL) {}};class Solution {public:    vector<int> preorderTraversal(TreeNode* root) {        vector<int> result;		stack<TreeNode*> nodes;		nodes.push(root);		TreeNode* node = NULL;		while(!nodes.empty())		{			node = nodes.top();			nodes.pop();			//如果当前结点非空，压入右孩子，在压入左孩子			if(node)			{				result.push_back(node->val);				nodes.push(node->right);				nodes.push(node->left);			}			//如果当前结点为空，下次继续弹出		}		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.preorderTraversal(root);		 print(result);		 deleteBinaryTree(root);	 }}int main(int argc , char* argv[]){	process();	getchar();	return 0;}