28
05/2015
[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
解题思路：
二叉树的前序遍历。题目要求用非递归的方法解答。那我们先看一下递归方法的解法。
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<int> preorderTraversal(TreeNode* root) {
vector<int> result;
preorderHelper(result, root);
return result;
}
void preorderHelper(vector<int>& 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<int> preorderTraversal(TreeNode* root) {
vector<int> result;
queue<TreeNode*> l;
stack<TreeNode*> 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;
}
};
0 条评论