?
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
解题思路：
二叉树的前序遍历。题目要求用非递归的方法解答。那我们先看一下递归方法的解法。
1、递归解法。
?
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector
preorderTraversal(TreeNode* root) {
vector
result; preorderHelper(result, root); return result; } void preorderHelper(vector
& result, TreeNode* root){ if(root==NULL){ return; } result.push_back(root->val); preorderHelper(result, root->left); preorderHelper(result, root->right); } };
2、非递归解法
?
我们可以用两个数据结构来存储中间状态。用队列来存储左孩子，用栈来存储右孩子。优先遍历所有左孩子。
?
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector
preorderTraversal(TreeNode* root) {
vector
result; queue
l; stack
r; if(root!=NULL){ l.push(root); } while(!l.empty()||!r.empty()){ TreeNode* node = NULL; if(!l.empty()){ node=l.front(); l.pop(); }else{ node=r.top(); r.pop(); } result.push_back(node->val); if(node->left!=NULL){ l.push(node->left); } if(node->right!=NULL){ r.push(node->right); } } return result; } };
?