Non-recursive traversal and reconstruction of binary tree

 在 数据结构  tagged tree by

参考来源：http://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html

二叉树的遍历是个老掉牙的问题，本文只是做个总结，并且给出正确的实现以便今后作为函数库使用。

首先总结四种遍历方式的非递归实现，递归实现太直截了当了，因此略去，对于先序、中序、后序三种遍历方式，同时给出使用栈辅助的 O(n) 空间复杂度的解法及不需要栈辅助的 O(1) 空间复杂度的 Morris 解法。

二叉树结点的定义如下（使用 LeetCode 题库里的定义）

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

先序遍历

栈辅助解法唯一的一个细节是入栈时右孩子先入栈，左孩子后入栈，仅此而已

std::vector<int> preorderTraversal(struct TreeNode *root)
{
    std::vector<int> res;
    if (root == NULL)
        return res;
    struct TreeNode *p = NULL;
    std::stack<struct TreeNode*> S;
    S.push(root);
    while (!S.empty())
    {
        p = S.top();
        S.pop();
        res.push_back(p->val);
        if (p->right != NULL)
            S.push(p->right);
        if (p->left != NULL)
            S.push(p->left);
    }
    return res;
}

Morris 解法借助了线索二叉树的概念，将叶子结点的左右指针域充分利用了起来，以便在遍历到叶子结点之后能够重新找到其父结点，详细解释可访问参考来源的博文链接

std::vector<int> preorderTraversal(struct TreeNode *root)
{
    std::vector<int> res;
    struct TreeNode *p = root;
    while (p != NULL)
    {
        if (p->left != NULL)
        {
            struct TreeNode *predecessor = p->left;
            while (predecessor->right != NULL && predecessor->right != p)
                predecessor = predecessor->right;
            if (predecessor->right == NULL)
            {
                predecessor->right = p;
                res.push_back(p->val);
                p = p->left;
            }
            else
            {
                predecessor->right = NULL;
                p = p->right;
            }
        }
        else
        {
            res.push_back(p->val);
            p = p->right;
        }
    }
    return res;
}

中序遍历

常规解法是先往最左边遍历到底，然后退回来一小步之后遍历右子树，然后又是往最左边遍历到底，这样不断重复，直至所有结点遍历完毕

std::vector<int> inorderTraversal(struct TreeNode *root)
{
    std::vector<int> res;
    std::stack<struct TreeNode*> S;
    struct TreeNode *p = root;
    while (!S.empty() || p != NULL)
    {
        if (p != NULL)
        {
            S.push(p);
            p = p->left;
        }
        else
        {
            p = S.top();
            S.pop();
            res.push_back(p->val);
            p = p->right;
        }
    }
    return res;
}

Morris 解法如下（Morris 解法的先序和中序的代码非常类似，区别就在什么时候访问结点）

std::vector<int> inorderTraversal(struct TreeNode *root)
{
    std::vector<int> res;
    struct TreeNode *p = root;
    while (p != NULL)
    {
        if (p->left != NULL)
        {
            struct TreeNode *predecessor = p->left;
            while (predecessor->right != NULL && predecessor->right != p)
                predecessor = predecessor->right;
            if (predecessor->right == NULL)
            {
                predecessor->right = p;
                p = p->left;
            }
            else
            {
                predecessor->right = NULL;
                res.push_back(p->val);
                p = p->right;
            }
        }
        else
        {
            res.push_back(p->val);
            p = p->right;
        }
    }
    return res;
}

后序遍历

栈辅助的解法中，需要使用一个额外的指针保存之前访问的那个结点，仅在确保一个结点的左右孩子结点都被访问之后才访问该结点，左右孩子结点入栈顺序也同先序遍历一样

std::vector<int> postorderTraversal(struct TreeNode *root)
{
    std::vector<int> res;
    if (root == NULL)
        return res;
    std::stack<struct TreeNode*> S;
    struct TreeNode *prev = NULL, *cur = NULL;
    S.push(root);
    while (!S.empty())
    {
        cur = S.top();
        /* visit cur when it is a leaf node or its childs have been visited */
        if ((cur->left == NULL && cur->right == NULL) || 
            prev != NULL && (prev == cur->left || prev == cur->right))
        {
            res.push_back(cur->val);
            S.pop();
            prev = cur;
        }
        else
        {
            /* push() right child first, left child second, so left child comes first when pop() */
            if (cur->right != NULL)
                S.push(cur->right);
            if (cur->left != NULL)
                S.push(cur->left);
        }
    }
    return res;
}

因为先序遍历的顺序是 “根、左、右”，根据先序遍历的 Morris 解法，程序做个对称很容易得到 “根、右、左” 的遍历序列，最后再对 std::vector 做个 reverse 就得到了 “左、右、根” 的后序遍历序列

std::vector<int> postorderTraversal(struct TreeNode *root)
{
    std::vector<int> res;
    struct TreeNode *p = root;
    while (p != NULL)
    {
        if (p->right != NULL)
        {
            struct TreeNode *successor = p->right;
            while (successor->left != NULL && successor->left != p)
                successor = successor->left;
            if (successor->left == NULL)
            {
                successor->left = p;
                res.push_back(p->val);
                p = p->right;
            }
            else
            {
                successor->left = NULL;
                p = p->left;
            }
        }
        else
        {
            res.push_back(p->val);
            p = p->left;
        }
    }
    std::reverse(res.begin(), res.end());
    return res;
}

层序遍历

层序遍历采用队列实现，众猿皆知

std::vector<std::vector<int> > levelorderTraversal(struct TreeNode *root)
{
    std::vector<std::vector<int> > res;
    if (root == NULL)
        return res;
    std::vector<int> level;
    std::queue<struct TreeNode*> Q;
    struct TreeNode *p = NULL;
    Q.push(root);
    int visited = 0, total = 1, nextTotal = 0;
    while (!Q.empty())
    {
        p = Q.front();
        Q.pop();
        level.push_back(p->val);
        if (p->left != NULL)
        {
            Q.push(p->left);
            ++nextTotal;
        }
        if (p->right != NULL)
        {
            Q.push(p->right);
            ++nextTotal;
        }
        if (++visited == total)
        {
            visited = 0;
            total = nextTotal;
            nextTotal = 0;
            res.push_back(level);
            level.clear();
        }
    }
    return res;
}

根据中序、先序重构二叉树

通过在中序序列中找到根结点（根结点在先序序列中总是位于最前面）将序列分成两部分，然后分治递归

struct TreeNode* reconstructByInPre(int *preOrder, int *preOrderEnd, int *inOrder, int *inOrderEnd)
{
    struct TreeNode *root = new struct TreeNode(*preOrder);

    if (preOrder == preOrderEnd)
        return root;

    int rootOffset = 0;
    while (inOrder != inOrderEnd && *preOrder != *inOrder)
        ++rootOffset, ++inOrder;
    if (rootOffset > 0)
        root->left = reconstructByInPre(preOrder + 1, preOrder + rootOffset, inOrder - rootOffset, inOrder - 1);
    if (inOrder != inOrderEnd)
        root->right = reconstructByInPre(preOrder + rootOffset + 1, preOrderEnd, inOrder + 1, inOrderEnd);

    return root;
}

struct TreeNode* reconstructBinaryTree(std::vector<int>& preorder, std::vector<int>& inorder)
{
    if (preorder.empty() || inorder.empty())
        return NULL;
    size_t L = preorder.size();
    return reconstructByInPre(preorder.data(), preorder.data() + L - 1, inorder.data(), inorder.data() + L - 1);
}

根据中序、后序重建二叉树

通过在中序序列中找到根结点（根结点在后序序列中总是位于最后面）将序列分成两部分，然后分治递归

struct TreeNode* reconstructByInPost(int *inOrder, int *inOrderEnd, int *postOrder, int *postOrderEnd)
{
    struct TreeNode *root = new struct TreeNode(*postOrderEnd);

    if (inOrder == inOrderEnd)
        return root;

    int rootOffset = 0;
    while (inOrder != inOrderEnd && *postOrderEnd != *inOrder)
        ++rootOffset, ++inOrder;
    if (rootOffset > 0)
        root->left = reconstructByInPost(inOrder - rootOffset, inOrder - 1, postOrder, postOrder + rootOffset - 1);
    if (inOrder != inOrderEnd)
        root->right = reconstructByInPost(inOrder + 1, inOrderEnd, postOrder + rootOffset, postOrderEnd - 1);

    return root;
}

struct TreeNode* buildTree(std::vector<int>& inorder, std::vector<int>& postorder)
{
    if (inorder.empty() || postorder.empty())
        return NULL;
    size_t L = inorder.size();
    return reconstructByInPost(inorder.data(), inorder.data() + L - 1, postorder.data(), postorder.data() + L - 1);
}

根据中序、层序重建二叉树

由于在中序序列划分之后得到的左右子树两部分在层序序列中是相互交错的，因此需要将层序序列拣选为对应于左右子树的两部分，随后才能进行递归，而且注意到参数 levelOrder 是值传递的，因此根据中序、层序重建二叉树的效率要比另外两种重建方式差些

struct TreeNode* reconstructByInLevel(int *inOrder, int *inOrderEnd, std::vector<int> levelOrder)
{
    struct TreeNode *root = new struct TreeNode(levelOrder[0]);

    if (levelOrder.size() == 1)
        return root;

    int rootOffset = 0;
    while (inOrder != inOrderEnd && *inOrder != levelOrder[0])
        ++rootOffset, ++inOrder;
    std::vector<int> leftSublevel, rigtSublevel;
    for (size_t i = 1; i < levelOrder.size(); ++i)
    {
        int *in = inOrder - rootOffset;
        for (; in != inOrder; ++in)
        {
            if (*in == levelOrder[i])
            {
                leftSublevel.push_back(levelOrder[i]);
                break;
            }
        }
        if (in == inOrder)
            rigtSublevel.push_back(levelOrder[i]);
    }
    if (rootOffset > 0)
        root->left = reconstructByInLevel(inOrder - rootOffset, inOrder - 1, leftSublevel);
    if (inOrder != inOrderEnd)
        root->right = reconstructByInLevel(inOrder + 1, inOrderEnd, rigtSublevel);

    return root;
}

struct TreeNode* buildTree(std::vector<int>& inorder, std::vector<int>& levelorder)
{
    if (inorder.empty() || levelorder.empty())
        return NULL;
    return reconstructByInLevel(inorder.data(), inorder.data() + inorder.size() - 1, levelorder);
}

Leave a comment

邮箱地址不会被公开。 必填项已用*标注