给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
数据范围：二叉树的节点数量满足 0≤n≤100 ，二叉树节点的值满足 1≤val≤100 ，树的各节点的值各不相同。
输入：{1,#,2,3} 返回值：[1,2,3]
二、递归方式 运行结果： 代码：class Solution {
public:
vector preorderTraversal(TreeNode* root) {
vector ans;
if(root == NULL) return ans;
preorder(root, ans);
return ans;
}
void preorder(TreeNode* root, vector& ret){
if(root == NULL) return;
ret.emplace_back(root->val);
preorder(root->left, ret);
preorder(root->right, ret);
}
};
二、非递归方式
运行结果：
代码：
class Solution {
public:
vector preorderTraversal(TreeNode* root) {
vector ans;
if(root == NULL) return ans;
stack st; //辅助栈
TreeNode* p = root;
while(p != NULL || !st.empty()){
while(p){
st.push(p);
ans.emplace_back(p->val);
p = p->left; //找到最左边的节点
}
if(!st.empty()){
p = st.top();
st.pop();
p = p->right; //转向处理右子树
}
}
return ans;
}
};
