二叉树的前序遍历---迭代算法

二叉树的前序遍历

　　二叉树的前序遍历过程相当于先访问最左边路径上的所有节点，然后在从后往前访问各个节点的右子树，

因此应该想到要使用栈结构。访问当前的节点的同时将其右子树节点放入栈中等待访问。先序遍历的代码如

下：

 vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> s;
        TreeNode* temp = root;
        // 当栈不为空或者root不为空节点时
        while(!s.empty() || temp){
        //`先遍历、访问、压栈左节点`
            while(temp){
                s.push(temp);
                res.push_back(temp->val);
                temp = temp->left;
            }
        //当访问节点不存在左子树时，退栈对右子树进行访问
            temp = s.top();
            s.pop();
            temp = temp->right;
        }
        return res;
    }

　　使用一个辅助栈的结构进行访问，访问当前的节点并将其右子树存入栈中，直到节点的左子树不存在时从栈中将节点取出，开始

迭代访问其右子树。