Leetcode: Binary Tree Preorder Traversal

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?

Recursive:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void preorder(TreeNode* root, vector<int> &path)
	{
		if(root!=NULL)
		{
			path.push_back(root->val);
			preorder(root->left, path);
			preorder(root->right, path);
		}
	}
	vector<int> preorderTraversal(TreeNode *root) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        vector<int> path;
		preorder(root, path);
		return path;
    }
};
           

Iterative:

vector<int> preorderTraversal(TreeNode *root) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        vector<int> path;
		stack<TreeNode*> stk;
		while(root != NULL || !stk.empty())
		{
			if(root != NULL)
			{
				while(root)
				{
					path.push_back(root->val);
					stk.push(root);
					root=root->left;
				}
			}
			else{
				root = stk.top()->right;
				stk.pop();
			}
		}
		return path;
    }
           

vector<int> preorderTraversal(TreeNode *root) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        vector<int> path;
		stack<TreeNode*> stk;
		if(root != NULL)
		{
			stk.push(root);
			while(!stk.empty())
			{
				root = stk.top();
				stk.pop();
				path.push_back(root->val);
				if(root->right)	stk.push(root->right);
				if(root->left) stk.push(root->left);
			}
		}
		return path;
    }
           

其他兩種非遞歸的周遊算法：

中序周遊-非遞歸：

vector<int> InOrderTraversal(TreeNode *root) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        vector<int> path;
		stack<TreeNode*> stk;
		while(root != NULL || !stk.empty())
		{
			while(root != NULL)
			{
				stk.push(root);
				root = root->left;
			}
			if( !stk.empty())
			{
				root = stk.top();
				stk.pop();
				root = root->right;
			}
		}

		return path;
    }
           

後序周遊-非遞歸：

struct TNode{
		//TreeNode* root;
		int val;
		TNode *left;
		TNode *right;
		bool isVisited;
		TNode(int a):val(a),left(NULL),right(NULL),isVisited(false){};
	};

	vector<int> PostOrderTraversal(TNode *root) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        vector<int> path;
		stack<TNode*> stk;
		if(root != NULL)
		{
			root->isVisited = false;
			stk.push(root);
		}
		TNode* cur = NULL;
		while(!stk.empty())
		{
			cur = stk.top();
			if(cur->isVisited)
			{
				path.push_back(cur->val);
				stk.pop();
			}else{
				cur->isVisited=true;
				if(cur->right)
				{
					cur->right->isVisited = false;
					stk.push(cur->right);
				}
				if(cur->left)
				{
					cur->left->isVisited = false;
					stk.push(cur->left);
				}
			}
		}
		return path;
    }