LeetCode:Binary Tree Preorder Traversal

图的先序遍历，由于上一题后序遍历使用的是递归的方法，所以我这次用的就是迭代。

跟递归一样，迭代也要注意两方面，一方面就是迭代循环的判断条件，相当于递归的出口，还有就是迭代的函数，跟递归的函数类似这题。

今天特意看了递归和迭代的原理，与其说递归是一种算法，其实递归更像是一种思想，一种方便我们考虑的思想，迭代就是一种结构，不断循环的结构。

为了理解递归的工作原理，你需要追踪递归调用的执行过程，所以让我们来进行这项工作。追踪一个递归函数的执行过程的关键是理解函数中所声明的变量是如何存储的。当函数被调用时，它的变量的空间是创建于运行时堆栈上的。以前调用的函数的变量扔保留在堆栈上，但他们被新函数的变量所掩盖，因此是不能被访问的。

　　当递归函数调用自身时，情况于是如此。每进行一次新的调用，都将创建一批变量，他们将掩盖递归函数前一次调用所创建的变量。当我追踪一个递归函数的执行过程时，必须把分数不同次调用的变量区分开来，以避免混淆。

我们可以举个例子：

给出一个值4267， 我们需要依次产生字符‘4’, ‘2’, ‘6’, ‘7’.

　　程序中的函数有两个变量：参数value和局部变量quotient。下面的一些图显示了堆栈的状态，当前可以访问的变量位于栈顶。所有其他调用的变量饰以灰色的阴影，表示他们不能被当前正在执行的函数访问。

　　不算递归调用语句本身，到目前为止所执行的语句只是除法运算以及对quotient的值进行测试。由于递归调用这些语句重复执行，所以它的效果类似循环：当quotient的值非零时，把它的值作为初始值重新开始循环。但是，递归调用将会保存一些信息（这点与循环不同），也就好是保存在堆栈中的变量值。这些信息很快就会变得非常重要。

　　现在quotient的值变成了零，递归函数便不再调用自身，而是开始打印输出。然后函数返回，并开始销毁堆栈上的变量值。

从这里我们可以看到，递归每做一次，就会单独分配一段连续存储空间，存放调用函数的实参，被调用函数的形参，控制转移地址，为局部变量开辟空间，注意！是每一次都会开辟空间，所以我们用递归的方法常常会出现栈溢出的情况。但是递归的好处就是比较接近于我们常人的思想。

对于大部分的递归函数，我们都可以模仿操作系统用堆栈的方式来消解递归，编程一个迭代函数。

/**
 * Definition for binary tree
 * 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> path;    
        stack<TreeNode* > stk; //堆栈保存树的信息 
        if(root==NULL)return path;
		stk.push(root);
		TreeNode* cur=root;
		while(!stk.empty()){
			cur=stk.top(); //指向栈顶元素 
			path.push_back(cur->val);//父节点压入数组 
			stk.pop();//父节点出栈 
			if(cur->right)stk.push(cur->right);//先今后出，所以先压入右子树 
			if(cur->left)stk.push(cur->left);
		} 
		return path;
        
    }
};

明天又腾讯跟阿里的实习笔试，祝我好运吧哈哈~

LeetCode:Binary Tree Preorder Traversal,布布扣,bubuko.com

LeetCode:Binary Tree Preorder Traversal

原文：http://blog.csdn.net/whu_sky/article/details/22400945