二叉树前序遍历的三种方法

在二叉树中序遍历的三种方法中介绍了中序遍历的三种方法：递归、迭代和Morris方法。其实，二叉树的其它遍历也有这三种遍历方法。这里介绍前序遍历的这三种方法。

1、递归法

调整下访问顺序即可。代码如下：

//recursion
class Solution1 {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ret;
        preHelper(ret,root);
        return ret;
    }
private:
    void preHelper(vector<int>& ret,TreeNode* root)
    {
        if(root==NULL)return;
        ret.push_back(root->val);
        preHelper(ret,root->left);
        preHelper(ret,root->right);
    }
};

2、迭代法

迭代法使用一个栈来保存当前不需要访问的节点。从根节点开始，访问当前节点，按照先右儿子后左儿子的顺序将当前节点的两个儿子压栈。当栈为空时说明遍历完毕。代码如下：

//iterative
class Solution2 {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ret;
        stack<TreeNode*> st;
        if(root==NULL)return ret;
        st.push(root);
        while(!st.empty())
        {
            TreeNode *curr=st.top();
            st.pop();
            if(curr->right)st.push(curr->right);
            if(curr->left)st.push(curr->left);
            ret.push_back(curr->val);
        }
        return ret;
    }
};

3、Morris方法

前序遍历和中序遍历的Morris方法基本一样，不同之处在访问的顺序。代码如下：

//Morris
class Solution3 {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ret;
        if(root==NULL)return ret;
        TreeNode *curr=root;
        TreeNode *pre;
        while(curr)
        {
            if(curr->left==NULL)
            {
                ret.push_back(curr->val);
                curr=curr->right;
            }
            else
            {
                pre=curr->left;
                while(pre->right&&pre->right!=curr)
                    pre=pre->right;
                if(pre->right==NULL)
                {
                    ret.push_back(curr->val);
                    pre->right=curr;
                    curr=curr->left;
                }
                else
                {
                    pre->right=NULL;
                    curr=curr->right;
                }
            }
        }
        return ret;
    }
};