学步园

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?

题目解析：

方案一：

递归方法

class Solution {
public:
    vector<int> preorderTraversal(TreeNode *root) {
        if(root == NULL)
            return res;
        res.push_back(root->val);
        preorderTraversal(root->left);
        preorderTraversal(root->right);
        return res;
    }
private:
    vector<int> res;
};

方案二：迭代方法

利用迭代，我们要借助栈来实现。

思路一：

对于前序遍历，我们可以让父节点入栈，当栈非空时开始遍历：出栈，访问结点，先放右孩子，再放左孩子；然后循环，知道栈为空。

这种思想很好理解，就跟层序遍历类似的想法，只不过这里是后进先出。

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> 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;
    }

扩展：完整的递归非递归在之前总结过：二叉树的递归和非递归遍历

另外参考：http://www.2cto.com/kf/201403/288184.html