题目

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

参考代码

递归算法很简单，如果不懂可以查看《大话数据结构》178页（PDF下载）。以下为迭代写法：

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {

        // 设置一个数组用来保存二叉树前序遍历的结果
        vector<int> preorderReslut;

        // 设置一个数组用来保存二叉树中序遍历的结果
        vector<int> inorderResult;

        // 设置一个数组用来保存二叉树后序遍历的结果
        vector<int> postorderResult;

        // 设置一个栈，用来保存路径
        stack<TreeNode*> st;

        // 设置一个节点，一开始指向根节点
        TreeNode* node = root;

        // 设置三种状态，方便表示当前遍历当前节点的时候进行到哪一步了
        // 每个节点都有 左、右、上 这三种状态
        // 按照 左 --> 右 --> 上 的顺序观察每个节点

        // 左代表该节点的左右孩子节点都没有遍历
        int nodeLeft = 100;

        // 右代表该节点的左孩子节点已经遍历，右孩子节点还没有遍历
        int nodeRight = 200;

        // 上代表左右孩子节点都已经遍历，需要返回到它的父节点
        int nodeUp = 300;

        // 每个节点的初始化状态都是从 左 开始
        int nodeState = nodeLeft;


        // 对二叉树进行遍历
        while(node != NULL){

            // 位置 ① 

            // 如果当前节点的状态是【左】，说明该节点的左右孩子节点都没有遍历
            if(nodeState  nodeLeft){
                // 把当前节点加入到二叉树前序遍历的结果数组中
                preorderReslut.push_back(node->val);

                // 如果当前节点有左子树
                if(node->left != NULL){

                    // 先把当前节点加入到栈中，用来记录节点移动的路径
                    st.push(node);

                    // 开始观察当前节点的左孩子节点，代码来到了位置 ① 
                    node = node->left;
                }else{

                    // 如果当前节点没有左子树，切换当前节点的状态为【右】
                    // 代码来到了位置 ① 
                    nodeState = nodeRight;
                }

            }else if(nodeState  nodeRight){ // 如果当前节点的状态是【右】，说明该节点的左孩子节点已经遍历，右孩子节点还没有遍历

                // 把当前节点加入到二叉树中序遍历的结果数组中
                // inorderResult.push_back(node->val);

                // 如果当前节点有右子树
                if(node->right != NULL){

                    // 先把当前节点加入到栈中，用来记录节点移动的路径
                    st.push(node);

                    // 开始观察当前节点的右孩子节点
                    node = node->right;

                    // 每个节点开始的状态都是【左】开始，所以需要重新设置一下节点的状态
                    nodeState = nodeLeft;

                    // 执行完上面三行代码，代码来到了位置 ①     

                }else{
                    // 如果当前节点没有右子树，切换当前节点的状态为【上】
                    // 代码来到了位置 ①
                    nodeState = nodeUp;
                }
            }else if(nodeState  nodeUp){ // 如果当前节点的状态是【上】，说明左右孩子节点都已经遍历，需要返回到它的父节点
                // 把当前节点加入到二叉树后序遍历的结果数组中
                //postorderResult.add(node.val);

                // 需要返回到当前节点的父节点位置，通过栈顶元素来获取当前节点的父节点
                // 首先构建一个空的节点
                TreeNode* parent = NULL;

                // 如果栈中有元素
                if(!st.empty()){

                    // 那么，栈顶元素就是当前节点的父节点
                    parent = st.top();
                    st.pop();

                    // 判断一下父节点的左节点是否为当前节点
                    // 比如这颗二叉树
                    //           1
                    //         /   \
                    //        2     3
                    //       / \     \
                    //      4   5     6
                    //  如果当前节点是 4 ，那么 4 的父节点是 2，2 的左孩子节点是 4，此时需要切换状态为【右】
                    //  如果当前节点是 5 ，那么 5 的父节点是 2，2 的左孩子节点是 4，此时不需要切换状态

                    // 如果父节点的左节点为当前节点
                    if(parent->left  node){
                        // 切换当前节点的状态为【右】
                        nodeState = nodeRight;
                    }
                }
                // 开始观察当前节点的父节点
                // 如果上述代码中栈中有元素，那么 parent 有值，代码来到了位置 ①
                // 如果上述代码中栈中没有元素，那么 parent 没有值，会跳出循环
                node = parent;

            }
        }

        // 根据题目要求，返回二叉树前序、中序、后序遍历的结果
        return preorderReslut;

    }