《剑指offer》面试题7：重建二叉树

马谦马谦马谦

615
文章

17
评论

2020年2月7日23:28:43数据结构和算法评论464字数 716阅读2分23秒阅读模式

一、题目

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不包含重复的数字。

例如，输入前序遍历序列[1, 2, 4, 7, 3, 5, 6, 8]和中序遍历序列[4, 7, 2, 1, 5, 3, 8, 6]，则重建如下图所示的二叉树并输出它的头结点：

《剑指offer》面试题7：重建二叉树-图片1

二、解析

根据前序、中序遍历的特性和上面的图形能得到的结论：

前序遍历的第一个元素就是树的根节点。
根节点左边的元素就是左子树，根右边的就是右子树。

图片描述：

《剑指offer》面试题7：重建二叉树-图片2

基于这两个特性就可以通过以下方式来构建出一颗二叉树：从前序遍历中确认根节点，再到中序遍历中找到定位到这个根节点，这样就可以拿到对应的左子树和右子树了。然后再按照相同的方式分别得到左右子树的子树，那么整个二叉树就可以构建起来了。

三、代码实现

二叉树节点定义：

template<typename T>
class tree_node {
    friend class bin_tree<T>;
    tree_node(const T &data) : data(data), lchild(nullptr), rchild(nullptr) {}
private:
    T data;
    tree_node *lchild;
    tree_node *rchild;
}

template<typename T>

class tree_node {

friend class bin_tree<T>;

tree_node(const T &data) : data(data), lchild(nullptr), rchild(nullptr) {}

private:

T data;

tree_node *lchild;

tree_node *rchild;

}

二叉树定义：

class bin_tree {
public:
    bin_tree() : root(nullptr) {}
    tree_node<T> *root;
};

class bin_tree {

public:

bin_tree() : root(nullptr) {}

tree_node<T> *root;

};

在二叉树类中实现通过前序遍历和中序遍历构造二叉树的函数：

/*
 * 根据前序和中序遍历序列构造一个二叉树
 * @pre_order 前序遍历序列
 * @in_order 中序遍历序列
 * @len 序列长度
 */
void construct(const T pre_order[], const T in_order[], const unsigned int len) {
    if (len < 1)
        return;

    this->root = construct_core(pre_order, pre_order + len - 1, 
            in_order, in_order + len - 1);
}

/*
 * 通过前序遍列和中序遍历的结果构建二叉树
 * 前序遍历序列[pre_order_start, pre_order_end]，中序遍历序列[in_order_start, in_order_end]
 * @pre_order_start 前序遍历的开始位置
 * @pre_order_end 前序遍历的结束位置
 * @in_order_start 中序遍历的开始位置
 * @in_order_end 中序遍历的结束位置
 */
tree_node<T> *construct_core(const T *pre_order_start, const T *pre_order_end,
                             const T *in_order_start, const T *in_order_end) {
    // 遍历指针
    const T *cursor;
    // 前序遍历序列中左子树的结束位置
    const T *lchild_end;
    // 左子树的长度
    unsigned int lchild_len;
    // 根节点
    tree_node<T> *root = nullptr;;

    // 前序遍历的首元素即为树根
    root = new tree_node<T>(pre_order_start[0]);

    // 如果前序遍历的头和尾相等，说明只有一个元素了，返回当前元素
    if (pre_order_start == pre_order_end) {
        // 下面是简单的判断输入参数是否合法
        // 如果只有一个元素了，前序和中序的遍历结果是相同的
        if (in_order_start == in_order_end && *in_order_start == *pre_order_start)
            return root;
        else // 输入有问题
            throw "invalid input";
    }

    // 在中序遍历中找到根节点
    cursor = in_order_start;
    while (cursor < in_order_end && *cursor != root->data)
        cursor++;

    // 匹配到中序遍历的最后一个元素了还没有找到，说明输入不合法
    if (cursor == in_order_end && *cursor != root->data)
        throw "invalid input";

    lchild_len = cursor - in_order_start;
    lchild_end = pre_order_start + lchild_len;

    // 递归获取左子树
    if (lchild_len > 0) {
        root->lchild = construct_core(pre_order_start + 1, lchild_end,
                                      in_order_start, cursor - 1);
    }

    // 递归获取右子树
    if (lchild_len < pre_order_end - pre_order_start) {
        root->rchild = construct_core(lchild_end + 1, pre_order_end,
                                      cursor + 1, in_order_end);
    }

    return root;
}

* 根据前序和中序遍历序列构造一个二叉树

* @pre_order 前序遍历序列

* @in_order 中序遍历序列

* @len 序列长度

void construct(const T pre_order[], const T in_order[], const unsigned int len) {

if (len < 1)

return;

this->root = construct_core(pre_order, pre_order + len - 1,

in_order, in_order + len - 1);

}

* 通过前序遍列和中序遍历的结果构建二叉树

* 前序遍历序列[pre_order_start, pre_order_end]，中序遍历序列[in_order_start, in_order_end]

* @pre_order_start 前序遍历的开始位置

* @pre_order_end 前序遍历的结束位置

* @in_order_start 中序遍历的开始位置

* @in_order_end 中序遍历的结束位置

tree_node<T> *construct_core(const T *pre_order_start, const T *pre_order_end,

const T *in_order_start, const T *in_order_end) {

// 遍历指针

const T *cursor;

// 前序遍历序列中左子树的结束位置

const T *lchild_end;

// 左子树的长度

unsigned int lchild_len;

// 根节点

tree_node<T> *root = nullptr;;

// 前序遍历的首元素即为树根

root = new tree_node<T>(pre_order_start[0]);

// 如果前序遍历的头和尾相等，说明只有一个元素了，返回当前元素

if (pre_order_start == pre_order_end) {

// 下面是简单的判断输入参数是否合法

// 如果只有一个元素了，前序和中序的遍历结果是相同的

if (in_order_start == in_order_end && *in_order_start == *pre_order_start)

return root;

else // 输入有问题

throw "invalid input";

}

// 在中序遍历中找到根节点

cursor = in_order_start;

while (cursor < in_order_end && *cursor != root->data)

cursor++;

// 匹配到中序遍历的最后一个元素了还没有找到，说明输入不合法

if (cursor == in_order_end && *cursor != root->data)

throw "invalid input";

lchild_len = cursor - in_order_start;

lchild_end = pre_order_start + lchild_len;

// 递归获取左子树

if (lchild_len > 0) {

root->lchild = construct_core(pre_order_start + 1, lchild_end,

in_order_start, cursor - 1);

}

// 递归获取右子树

if (lchild_len < pre_order_end - pre_order_start) {

root->rchild = construct_core(lchild_end + 1, pre_order_end,

cursor + 1, in_order_end);

}

return root;

}

四、单元测试

单元测试覆盖以下几点：

树为空
树只有一个节点
完全二叉树
满二叉树
不完全二叉树

4.1 树为空

/*
 * 测试：通过前序和中序便利序列构造二叉树
 * 案例：二叉树包含一个节点
 */
TEST(construct_by_pre_order_and_in_order, one_node) {
    bin_tree<int> tree;
    int data[1] = {1};
    tree.construct(data, data, 1);
    EXPECT_TRUE(tree.get_root());
    EXPECT_FALSE(tree.get_root()->get_lchild());
    EXPECT_FALSE(tree.get_root()->get_rchild());
}

* 测试：通过前序和中序便利序列构造二叉树

* 案例：二叉树包含一个节点

TEST(construct_by_pre_order_and_in_order, one_node) {

bin_tree<int> tree;

int data[1] = {1};

tree.construct(data, data, 1);

EXPECT_TRUE(tree.get_root());

EXPECT_FALSE(tree.get_root()->get_lchild());

EXPECT_FALSE(tree.get_root()->get_rchild());

}

4.2 树只有一个节点

/*
 * 测试：通过前序和中序便利序列构造二叉树
 * 案例：二叉树包含一个节点
 */
TEST(construct_by_pre_order_and_in_order, one_node) {
    bin_tree<int> tree;
    int data[1] = {1};
    tree.construct(data, data, 1);
    EXPECT_TRUE(tree.get_root());
    EXPECT_FALSE(tree.get_root()->get_lchild());
    EXPECT_FALSE(tree.get_root()->get_rchild());
}

* 测试：通过前序和中序便利序列构造二叉树

* 案例：二叉树包含一个节点

TEST(construct_by_pre_order_and_in_order, one_node) {

bin_tree<int> tree;

int data[1] = {1};

tree.construct(data, data, 1);

EXPECT_TRUE(tree.get_root());

EXPECT_FALSE(tree.get_root()->get_lchild());

EXPECT_FALSE(tree.get_root()->get_rchild());

}

4.3 完全二叉树

/*
 * 测试：通过前序和中序便利序列构造二叉树
 * 案例：完全二叉树测试
 *          1
 *        2   3
 *       4 5
 */
TEST(construct_by_pre_order_and_in_order, complete_bin_tree) {
    int pre_order[7] = {1, 2, 4, 5, 3};
    int in_order[7] = {4, 2, 5, 1, 3};
    bin_tree<int> tree;
    const tree_node<int> *root, *node;
    tree.construct(pre_order, in_order, 5);
    root = tree.get_root();
    EXPECT_TRUE(root);

    EXPECT_EQ(root->get_data(), 1);
    EXPECT_TRUE(root->get_lchild());
    EXPECT_TRUE(root->get_rchild());
    EXPECT_EQ(root->get_lchild()->get_data(), 2);
    EXPECT_EQ(root->get_rchild()->get_data(), 3);

    node = root->get_lchild(); // -> 节点2
    // 检查子节点
    EXPECT_TRUE(node->get_lchild());
    EXPECT_TRUE(node->get_rchild());
    EXPECT_EQ(node->get_lchild()->get_data(), 4);
    EXPECT_EQ(node->get_rchild()->get_data(), 5);
    // 检查子节点的子节点
    EXPECT_FALSE(node->get_lchild()->get_lchild());
    EXPECT_FALSE(node->get_lchild()->get_rchild());
    EXPECT_FALSE(node->get_rchild()->get_lchild());
    EXPECT_FALSE(node->get_rchild()->get_rchild());

    node = root->get_rchild(); // -> 节点3
    // 检查子节点
    EXPECT_FALSE(node->get_lchild());
    EXPECT_FALSE(node->get_rchild());
}

* 测试：通过前序和中序便利序列构造二叉树

* 案例：完全二叉树测试

* 1

* 2 3

* 4 5

TEST(construct_by_pre_order_and_in_order, complete_bin_tree) {

int pre_order[7] = {1, 2, 4, 5, 3};

int in_order[7] = {4, 2, 5, 1, 3};

bin_tree<int> tree;

const tree_node<int> *root, *node;

tree.construct(pre_order, in_order, 5);

root = tree.get_root();

EXPECT_TRUE(root);

EXPECT_EQ(root->get_data(), 1);

EXPECT_TRUE(root->get_lchild());

EXPECT_TRUE(root->get_rchild());

EXPECT_EQ(root->get_lchild()->get_data(), 2);

EXPECT_EQ(root->get_rchild()->get_data(), 3);

node = root->get_lchild(); // -> 节点2

// 检查子节点

EXPECT_TRUE(node->get_lchild());

EXPECT_TRUE(node->get_rchild());

EXPECT_EQ(node->get_lchild()->get_data(), 4);

EXPECT_EQ(node->get_rchild()->get_data(), 5);

// 检查子节点的子节点

EXPECT_FALSE(node->get_lchild()->get_lchild());

EXPECT_FALSE(node->get_lchild()->get_rchild());

EXPECT_FALSE(node->get_rchild()->get_lchild());

EXPECT_FALSE(node->get_rchild()->get_rchild());

node = root->get_rchild(); // -> 节点3

// 检查子节点

EXPECT_FALSE(node->get_lchild());

EXPECT_FALSE(node->get_rchild());

}

4.4 满二叉树

/*
 * 测试：通过前序和中序便利序列构造二叉树
 * 案例：满二叉树测试
 *          1
 *        2   3
 *       4 5 6 7
 */
TEST(construct_by_pre_order_and_in_order, full_bin_tree) {
    int pre_order[7] = {1, 2, 4, 5, 3, 6, 7};
    int in_order[7] = {4, 2, 5, 1, 6, 3, 7};
    bin_tree<int> tree;
    const tree_node<int> *root, *node;
    tree.construct(pre_order, in_order, 7);
    root = tree.get_root();
    EXPECT_TRUE(root);

    EXPECT_EQ(root->get_data(), 1);
    EXPECT_TRUE(root->get_lchild());
    EXPECT_TRUE(root->get_rchild());
    EXPECT_EQ(root->get_lchild()->get_data(), 2);
    EXPECT_EQ(root->get_rchild()->get_data(), 3);

    node = root->get_lchild(); // -> 节点2
    // 检查子节点
    EXPECT_TRUE(node->get_lchild());
    EXPECT_TRUE(node->get_rchild());
    EXPECT_EQ(node->get_lchild()->get_data(), 4);
    EXPECT_EQ(node->get_rchild()->get_data(), 5);
    // 检查子节点的子节点
    EXPECT_FALSE(node->get_lchild()->get_lchild());
    EXPECT_FALSE(node->get_lchild()->get_rchild());
    EXPECT_FALSE(node->get_rchild()->get_lchild());
    EXPECT_FALSE(node->get_rchild()->get_rchild());

    node = root->get_rchild(); // -> 节点3
    // 检查子节点
    EXPECT_TRUE(node->get_lchild());
    EXPECT_TRUE(node->get_rchild());
    EXPECT_EQ(node->get_lchild()->get_data(), 6);
    EXPECT_EQ(node->get_rchild()->get_data(), 7);
    // 检查子节点的子节点
    EXPECT_FALSE(node->get_lchild()->get_lchild());
    EXPECT_FALSE(node->get_lchild()->get_rchild());
    EXPECT_FALSE(node->get_rchild()->get_lchild());
    EXPECT_FALSE(node->get_rchild()->get_rchild());
}

* 测试：通过前序和中序便利序列构造二叉树

* 案例：满二叉树测试

* 1

* 2 3

* 4 5 6 7

TEST(construct_by_pre_order_and_in_order, full_bin_tree) {

int pre_order[7] = {1, 2, 4, 5, 3, 6, 7};

int in_order[7] = {4, 2, 5, 1, 6, 3, 7};

bin_tree<int> tree;

const tree_node<int> *root, *node;

tree.construct(pre_order, in_order, 7);

root = tree.get_root();

EXPECT_TRUE(root);

EXPECT_EQ(root->get_data(), 1);

EXPECT_TRUE(root->get_lchild());

EXPECT_TRUE(root->get_rchild());

EXPECT_EQ(root->get_lchild()->get_data(), 2);

EXPECT_EQ(root->get_rchild()->get_data(), 3);

node = root->get_lchild(); // -> 节点2

// 检查子节点

EXPECT_TRUE(node->get_lchild());

EXPECT_TRUE(node->get_rchild());

EXPECT_EQ(node->get_lchild()->get_data(), 4);

EXPECT_EQ(node->get_rchild()->get_data(), 5);

// 检查子节点的子节点

EXPECT_FALSE(node->get_lchild()->get_lchild());

EXPECT_FALSE(node->get_lchild()->get_rchild());

EXPECT_FALSE(node->get_rchild()->get_lchild());

EXPECT_FALSE(node->get_rchild()->get_rchild());

node = root->get_rchild(); // -> 节点3

// 检查子节点

EXPECT_TRUE(node->get_lchild());

EXPECT_TRUE(node->get_rchild());

EXPECT_EQ(node->get_lchild()->get_data(), 6);

EXPECT_EQ(node->get_rchild()->get_data(), 7);

// 检查子节点的子节点

EXPECT_FALSE(node->get_lchild()->get_lchild());

EXPECT_FALSE(node->get_lchild()->get_rchild());

EXPECT_FALSE(node->get_rchild()->get_lchild());

EXPECT_FALSE(node->get_rchild()->get_rchild());

}

4.5 非完全二叉树

/*
 * 测试：通过前序和中序便利序列构造二叉树
 * 案例：普通二叉树测试
 *          1
 *        2   3
 *         5 6
 */
TEST(construct_by_pre_order_and_in_order, normal_bin_tree) {
    int pre_order[7] = {1, 2, 5, 3, 6};
    int in_order[7] = {2, 5, 1, 6, 3};
    bin_tree<int> tree;
    const tree_node<int> *root, *node;
    tree.construct(pre_order, in_order, 5);
    root = tree.get_root();
    EXPECT_TRUE(root);

    EXPECT_EQ(root->get_data(), 1);
    EXPECT_TRUE(root->get_lchild());
    EXPECT_TRUE(root->get_rchild());
    EXPECT_EQ(root->get_lchild()->get_data(), 2);
    EXPECT_EQ(root->get_rchild()->get_data(), 3);

    node = root->get_lchild(); // -> 节点2
    // 检查子节点
    EXPECT_FALSE(node->get_lchild());
    EXPECT_TRUE(node->get_rchild());
    EXPECT_EQ(node->get_rchild()->get_data(), 5);
    // 检查子节点的子节点
    EXPECT_FALSE(node->get_rchild()->get_lchild());
    EXPECT_FALSE(node->get_rchild()->get_rchild());

    node = root->get_rchild(); // -> 节点3
    // 检查子节点
    EXPECT_TRUE(node->get_lchild());
    EXPECT_FALSE(node->get_rchild());
    // 左子节点为6，右子节点为空
    EXPECT_EQ(node->get_lchild()->get_data(), 6);
    // 检查子节点的子节点
    EXPECT_FALSE(node->get_lchild()->get_lchild());
    EXPECT_FALSE(node->get_lchild()->get_rchild());
}