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].
解法一：
递归方法：
如果root不为空，
先访问根，递归左子树，递归右子树。
void preorderCore(TreeNode *root,vector<int> &res){
if(root){
res.push_back(root->val);
preorderCore(root->left,res);
preorderCore(root->right,res);
}
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
preorderCore(root,res);
return res;
}解法二：
使用栈，迭代方法。
void preorderCore(TreeNode *root,vector<int> &res){
if(!root)
return;
stack<TreeNode*> st;
while(!st.empty()||root){
while(root){
st.push(root);
res.push_back(root->val);
root=root->left;
}
root=st.top();
st.pop();
root=root->right;
}
}
另一种写法为：
void preorderCore(TreeNode *root,vector<int> &res){
if(!root)
return;
stack<TreeNode*> st;
st.push(root);
while(!st.empty()){
root=st.top();
st.pop();
res.push_back(root->val);
if(root->right)
st.push(root->right);
if(root->left)
st.push(root->left);
}
}144. Binary Tree Preorder Traversal——递归，非递归
原文：http://searchcoding.blog.51cto.com/1335412/1752603