LeetCode Binary Tree Preorder Traversal 앞의 두 갈래 트리 귀속과 비귀속 해법 반복

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?
2014-1-10 update:
순서대로 반복하는 비귀속도 매우 간단하다.

vector<int> preorderTraversal(TreeNode *root) 
	{
		vector<int> rs;
		if (!root) return rs;

		stack<TreeNode *> stk;
		stk.push(root);
		while (!stk.empty())
		{
			TreeNode *t = stk.top();
			stk.pop();
			rs.push_back(t->val);
			if (t->right) stk.push(t->right);
			if (t->left) stk.push(t->left);
		}
		return rs;
	}

확실히 노트에서 말한 바와 같이 귀속을 사용하는 데는 몇 분만 걸리면 해결된다. 귀속을 사용하지 않으면 스스로 궁리하는 데 30분이 채 걸리지 않는다.
코드를 보면 비귀속이 귀속보다 훨씬 길다는 것을 알 수 있다.
비귀속 방법의 주요 난점:
1. 두 개의 순환을 사용해야 한다. 왼쪽 트리 순환은 오른쪽 트리 순환을 끼워 넣는다.
2. 오른쪽 나무가 있을 때 이 순환에서 벗어나 다시 왼쪽 나무 순환으로 들어가야 한다.
2. 왼쪽 나무가 없을 때는 빈 나무가 나올 때까지 기다리지 않고 창고를 나가야 한다.
다음은 두 가지 방법으로 이 문제를 해결해 보겠습니다. 그들의 시간 효율은 모두 많지 않습니다. 모두 12ms입니다. 대략 테스트 데이터가 매우 적기 때문에 시간은 모두 같습니다.Leet Code의 한 문제이기도 해요. 테스트 데이터가 많지 않아요.
기본 함수는 동일합니다.

vector<int> preorderTraversal(TreeNode *root) {
		vector<int> prePath; 
		preStack(root, prePath);
		return prePath;
	}

귀속법:
 

void preNodes(TreeNode *node,vector<int> &onePath)
	{
		if(node == nullptr) return;
		onePath.push_back(node->val);
		preNodes(node->left, onePath);
		preNodes(node->right, onePath);
	}

비귀속법:
 

void preStack(TreeNode *node, vector<int> &prePath)
	{
		if(node == nullptr) return;
		stack<TreeNode *> stk;
		TreeNode *cur = node;
		stk.push(cur);
		while (!stk.empty())
		{
			cur = stk.top();
			prePath.push_back(cur->val);
			while (cur->left)
			{
				prePath.push_back(cur->left->val);
				cur = cur->left;
				stk.push(cur);
			}
			stk.pop();
			while (!stk.empty() || cur->right)
			{
				if(cur->right)
				{
					cur = cur->right;
					stk.push(cur);
					break;
				}
				else
				{
					cur = stk.top();
					stk.pop();
				}
			}//while
		}//while
	}

//2014-2-19 update
	vector<int> preorderTraversal(TreeNode *root) 
	{
		vector<int> rs;
		if (!root) return rs;
		stack<TreeNode *> stk;
		stk.push(root);
		while (!stk.empty())
		{
			TreeNode *t = stk.top();
			stk.pop();
			rs.push_back(t->val);
			if (t->right) stk.push(t->right);
			if (t->left) stk.push(t->left);
		}
		return rs;
	}