二叉树的前序遍历-C++两种方式-牛客BM23

一、题目

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

数据范围：二叉树的节点数量满足 0≤n≤100  ，二叉树节点的值满足 1≤val≤100  ，树的各节点的值各不相同。

 输入：{1,#,2,3}    返回值：[1,2,3]

二、递归方式

运行结果：

代码：

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        if(root == NULL) return ans;
        preorder(root, ans);
        return ans;
    }
    void preorder(TreeNode* root, vector<int>& ret){
        if(root == NULL) return;
        ret.emplace_back(root->val);
        preorder(root->left, ret);
        preorder(root->right, ret);
    }
};

二、非递归方式

运行结果：

代码：

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        if(root == NULL) return ans;
        stack<TreeNode*> 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;
    }
};