题解 | #先序遍历非递归——二叉树的前序遍历#

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <stack>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型vector
     */
    //先序遍历的非递归算法需要用到一个辅助栈存储遍历路径上节点的地址；
    void pre_order(TreeNode* Node,vector<int> &ans){
        if(Node == NULL) return;
        stack<TreeNode*> s; //辅助数组
        s.push(Node);//根节点压入辅助栈
        while (!s.empty()) {
            TreeNode* temp = s.top();
            s.pop();
            ans.push_back(temp->val);
            //注意栈是先进后出 先序遍历中是先访问左子树，所以一定要先压入右子树
            if(temp->right)
                s.push(temp->right);
            if(temp->left)
                s.push(temp->left);
        }
    }
    vector<int> preorderTraversal(TreeNode* root) {
        // write code here
        vector<int> ans;
        pre_order(root, ans);
        return ans;
    }
};