[算法笔记] PAT-ADV-1020

题目要求：给出二叉树的后序遍历序列和中序遍历序列，输出二叉树的层次遍历序列。

Sample Input

7

2 3 1 5 7 6 4

1 2 3 4 5 6 7

Sample Output

4 1 6 3 5 7 2

解题思路

首先，我们在数据结构课程中学过下面的结论：

后序遍历：左右根
中序遍历：左根右

显然，后序序列中的最后一个元素总是某个子树的根，叶子节点也算是一个子树 (可能你觉得这是一句废话)。

此外，只要确定根，那么可以在中序的某一片段序列中 “分离” 出左右子树。

下面我们来分析一下 Sample ，解析如何从如上2个结论唯一确定一颗二叉树。

在后序序列中：

2 3 1 5 7 6 4

4 毫无疑问是整个二叉树的根。现在在中序序列中找出 4 的位置。

1 2 3 4 5 6 7

也就是说可以得到二叉树的基本结构如下：

图1

        4

       / \

  1,2,3   5,6,7

再看后序序列剩下的元素：

2 3 1 5 7 6

最后一个元素是 6，说明在 6 是根。

在中序序列中：

1 2 3 | 4 | 5 6 7

说明在图1 中， 6 是右子树的根。

继续遍历后序序列：

2 3 1 5 7

5 和 7 既是叶子节点也是一个特殊的根。

此时，后序序列剩下：

2 3 1

中序序列为：

1 2 3

显然， 1 是根， 2 和 3 是 1 的右子树。以此类推， 2 是 3 的左子树。那么中序序列和后序序列唯一确定的二叉树如下：

概括一下算法要点：

从右往左遍历后序序列，得到根
在中序序列中找到根，分离出左右子树
对左右子树进行同样的操作

不难看出，是一个递归。

数据结构课程上，在纸上这类题目大家都会画出来，但是一到 Code 层面，完整实现还是有点难度的。

最后解析一下代码实现。

参数 l 和 r: 中序序列inorder[l...r]，代表当前所处理的子树
rootIdxPost: 后序序列中根的位置。(实际上取值变化就是: (N-1), ..., 0 )

Tree createTree(int l, int r, int &rootIdxPost)

{

    if (l > r)

        return NULL;

    if (l == r)

    {

        Tree t = new TreeNode(inorder[l]);

        rootIdxPost--;

        return t;

    }

    int rootVal = postorder[rootIdxPost--];

    int rootIdxIn = findRoot(inorder, rootVal);

    Tree root = new TreeNode(rootVal);

    root->right = createTree(rootIdxIn + 1, r, rootIdxPost);

    root->left = createTree(l, rootIdxIn - 1, rootIdxPost);

    return root;

}

完整代码：

#include <cstdio>

#include <vector>

#include <assert.h>

#include <queue>

#define NMAX 35

using namespace std;

struct TreeNode

{

    int val;

    TreeNode *left, *right;

    TreeNode(int v = -1, TreeNode *l = NULL, TreeNode *r = NULL) : val(v), left(l), right(r) {}

};

typedef TreeNode *Tree;

vector<int> postorder(NMAX), inorder(NMAX);

int N = 0;

int findRoot(vector<int> &inorder, int rootVal)

{

    size_t len = inorder.size();

    for (size_t i = 0; i < len; i++)

    {

        if (inorder[i] == rootVal)

            return i;

    }

    assert(0);

    return -1;

}

Tree createTree(int l, int r, int &rootIdxPost)

{

    if (l > r)

        return NULL;

    if (l == r)

    {

        Tree t = new TreeNode(inorder[l]);

        rootIdxPost--;

        return t;

    }

    int rootVal = postorder[rootIdxPost--];

    int rootIdxIn = findRoot(inorder, rootVal);

    Tree root = new TreeNode(rootVal);

    root->right = createTree(rootIdxIn + 1, r, rootIdxPost);

    root->left = createTree(l, rootIdxIn - 1, rootIdxPost);

    return root;

}

void level(Tree root)

{

    if (root == NULL)

        return;

    queue<Tree> q;

    printf("%d", root->val);

    if (root->left)

        q.push(root->left);

    if (root->right)

        q.push(root->right);

    while (!q.empty())

    {

        Tree p = q.front();

        q.pop();

        printf(" %d", p->val);

        if (p->left)

            q.push(p->left);

        if (p->right)

            q.push(p->right);

    }

}

int main()

{

    scanf("%d", &N);

    for (int i = 0; i < N; i++)

    {

        scanf("%d", &postorder[i]);

    }

    for (int i = 0; i < N; i++)

    {

        scanf("%d", &inorder[i]);

    }

    int rootIdxPost = N - 1;

    Tree root = createTree(0, N - 1, rootIdxPost);

    level(root);

}

markdown写bolg，＂那是真的niubility＂。

巴特西

[算法笔记] PAT-ADV-1020

Sample Input

Sample Output

解题思路

最新文章

热门文章