二叉树的前序遍历——非递归版本

1.题目解析

题目来源：144.二叉树的前序遍历——力扣

测试用例

2.算法原理 

前序遍历： 按照根节点->左子树->右子树的顺序遍历二叉树 

二叉树的前序遍历递归版本十分简单，但是如果树的深度很深会有栈溢出的风险，这里的非递归版本可以很好的规避这个缺点，这里的思路是运用栈与子问题套子问题

1.首先从最上面的根节点开始不断将左节点入栈直到叶子结点，然后将栈中的节点取出，并将该节点的右子树节点入栈，若为空则不入栈，

2.以此类推由头到左子树根部再向上遍历到右子树，右子树是同样的思路，最终栈为空且节点为空则结束即可

3.实战代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) 
    {
        vector<int> v;
        stack<TreeNode*> st;
        TreeNode* cur = root;

        while(cur || !st.empty())
        {
            //依次访问从最头结点向下遍历的左子树并入栈
            //当访问到底时向上取出栈内节点，访问其右子树
            //以此类推访问到整棵二叉树
            while(cur)
            {
                v.push_back(cur->val);
                st.push(cur);
                cur = cur->left;
            }

            //此时需要访问栈顶节点的右子树
            TreeNode* top = st.top();
            st.pop();

            cur = top->right;
        }
        return v;
    }
};