5.1.1二叉树的先序遍历

• • 1.题目
  • 2.代码

• 题目要求

• 思路
  （1）用到stack来辅助运算。由于先序遍历的顺序是"根-左-右", 算法为：
  把根节点 push 到栈中；
  （2）循环检测栈是否为空，若不空，则取出栈顶元素，保存其值，然后看其右子节点是否存在，若存在则 push 到栈中。再看其左子节点，若存在，则 push 到栈中；
  （3）题目要求不能使用递归

• eg：
  
  输入：root = [1,null,2,3]
  输出：[1,2,3]

• 递归参考

class Solution{
public:
	vector preorderTraversal(TreeNode* root){
	vector result;
	stack stack_Tree;
	if (!root)
		stack_Tree.push(root);
	
	while (!stack_Tree.empty())
	{
			const TreeNode* head=stack_Tree.top();
			stack_Tree.pop();
			result.push_back(head->val);
			
			看上面的eg分析得到
			if (!root->right)
				stack_Tree.push(root->right);

			
			if (!root->left)
				stack_Tree.push(root->left);
	}
	return result;
	}
};


递归方法，纯粹练习递归

class Solution{
public:
	vector result;
	vector preorderTraversal(TreeNode* root){
		if (!root)
			return result;
		transvers(root);
		return result;
	}
	
	void transvers(TreeNode* node)
	{
		if (!node)
			return;
		result.push_back(node->val);
		transvers(node->left);
		transvers(node->right);
	}

};