非递归遍历二叉树

Saturday, May 23, 2020

二叉树的非递归遍历基于栈, 代码风格不像递归遍历那么简洁统一,不太好记,聊以备忘

代码来自 这篇文章 ,作者在文章中统一了三种非递归遍历的风格,对于前序和中序遍历我还是更喜欢传统的写法,后序遍历采用了文章作者的写法

非递归前序遍历

//非递归前序遍历
void preorderTraversal(TreeNode *root, vector<int> &path)
{
    stack<TreeNode *> s;
    TreeNode *p = root;
    while(p != nullptr || !s.empty())
    {
        while(p != nullptr)
        {
            path.push_back(p->val);
            s.push(p);
            p = p->left;
        }
        if(!s.empty())
        {
            p = s.top();
            s.pop();
            p = p->right;
        }
    }
}

非递归中序遍历

//非递归中序遍历
void inorderTraversal(TreeNode *root, vector<int> &path)
{
    stack<TreeNode *> s;
    TreeNode *p = root;
    while(p != nullptr || !s.empty())
    {
        while(p != nullptr)
        {
            s.push(p);
            p = p->left;
        }
        if(!s.empty())
        {
            p = s.top();
            path.push_back(p->val);
            s.pop();
            p = p->right;
        }
    }
}

非递归后序遍历

//非递归后序遍历
void postorderTraversalNew(TreeNode *root, vector<int> &path)
{
    stack< pair<TreeNode *, bool> > s;
    s.push(make_pair(root, false));
    bool visited;
    while(!s.empty())
    {
        root = s.top().first;
        visited = s.top().second;
        s.pop();
        if(root == nullptr)
            continue;
        if(visited)
        {
            path.push_back(root->val);
        }
        else
        {
            s.push(make_pair(root, true));
            s.push(make_pair(root->right, false));
            s.push(make_pair(root->left, false));
        }
    }
}
algorithm

c++中++i和i++的区别

SUID、SGID 和 SBIT