144. Binary Tree Preorder Traversal

提交网址： https://leetcode.com/problems/binary-tree-preorder-traversal/

Total Accepted: 118355 Total Submissions: 297596 Difficulty: Medium

Given a binary tree, return the preorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1

    \

     2

    /

   3

return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

分析：

借助栈实现非递归先序遍历算法的方法如下：
1）将二叉树的根结点作为当前结点。
2）若当前结点非空，则先访问该结点，并将该结点进栈，再将其左孩子结点作为当前结点，重复步骤2)，直到当前结点为NULL为止。
3）若栈非空，则栈顶结点出栈，并将当前结点的右孩子结点作为当前结点。
4）重复步骤2）、3)，直到栈为空且当前结点为NULL为止。

AC代码：

#include<iostream>

#include<vector>

#include<stack>

using namespace std;

struct TreeNode

{

	int val;

	TreeNode *left, *right;

	TreeNode(int x): val(x), left(NULL), right(NULL) {}

};

class Solution

{

public:

	vector<int> preorderTraversal(TreeNode *root)

	{

	vector<int> res;

	TreeNode *p;

	stack<TreeNode*> s;

	p=root;

	while(!s.empty() || p!=NULL)

	{

		if(p!=NULL)

		{

			res.push_back(p->val);

			s.push(p);

			p=p->left;

		}

		if(p==NULL)

		{

			p=s.top();

			s.pop();

			p=p->right;

		}

	}

	return res;

}

};

// 以下为测试部分

/*

int main()

{

	Solution sol;

	vector<int> res;

	TreeNode *root = new TreeNode(1);

    root->right = new TreeNode(2);

    root->right->left = new TreeNode(3); 

	res=sol.preorderTraversal(root);

	for(int i:res)

		cout<<i<<" ";  // 此处为vector遍历的方法，C++11标准支持

	return 0;

}

*/