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

以你之姓@ 2022-08-09 13:51 71阅读 0赞

在[二叉树中序遍历的三种方法][Link 1]中介绍了中序遍历的三种方法：递归、迭代和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;
        }
    };

[Link 1]: http://http://blog.csdn.net/u012877472/article/details/49401751