C++20 出来了，怎么构造二叉树？

知识点速查

构造二叉树 Click

中序与前序或后序联合构造二叉树

这算是经典题目了吧，本科算法课上学到树这一节时的必做题，题目本身没什么难度，但这里比较有意思的是考虑代码的简洁与优雅程度。

首先，来讲一下算法思路。很简单，把树的构造看作是一个递归的过程。对于中序与前序，我们都知道中序序列是先遍历左子树，然后遍历根结点，再遍历右子树。而前序序列是先遍历根结点，然后遍历左子树，再遍历右子树。

那么怎么把它转化成一个递归问题呢？我们知道左子树也是通过左子树的中序序列和它的前序序列构造，右子树同理，那么只要在输入的中序序列中找到左子树的中序序列、在输入的前序序列中找到左子树的前序序列，那么就可以转化成与原问题相同的问题。而这一点是可以轻松做到的，通过前序的遍历顺序可以知道，它第一个遍历的一定是根结点，我们直接拿着这个根结点去中序序列中查找，找到根结点的位置，这样中序序列就被一分为二了，前半部是左子树的中序序列，后半部分是右子树的中序序列。同时，我们知道了左子树的大小（即其中结点的数量）。又因为前序序列是按“中左右”的顺序遍历，跳过“中”之前理所当然是“左”了，于是左子树的前序序列就是当前位置前进一位（跳过根结点）的位置开始，一直数左子树大小个元素。

这样，我们就有了左子树的中序序列和前序序列。同理，我们找到右子树的中序序列与前序序列。这时，问题就变成了非常简单的三步：

构造左子树与右子树
创建根结点
连接根结点与左子树和右子树

按这个思路，理想中的代码应该是：

1
2
3
4
5
6
7
8
TreeNode *build(inorder, preorder) {
    // trivial handlings...
    // ...
    root = new TreeNode(root_val);
    root->left = build(inorder_left_tree, preorder_left_tree);
    root->right = build(inorder_right_tree, preorder_right_tree);
    return root;
}

在 Python 中这种风格能轻易地通过切片做到，然而 C++ 中却不支持这种操作。从官方题解来看，为了顺利递归不得不再定义一个辅助函数，这个辅助函数有多至 6 个参数，包括中序序列、前序序列、中序序列的范围（两个参数）、前序序列的范围。这种写法看上去不够简洁，直观上能想到的改进方法是定义一个聚合类：

1
2
3
4
5
template<typename Iter>
struct OrderRange {
  Iter beg;
  Iter end;
};

然后辅助函数只用接收两个这样的 OrderRange 。但这样是行不通的，因为在递归的过程中总要对范围的有效性进行限制，比如在范围往前移动时，我们要限制它不能超过原来的序列末尾。这么来看，只有两个 OrderRange 是不够的，再增加参数个数明显违背了一开始追求简洁的初心。

我翻了翻 2020 年提交的代码，里面为了简洁程度居然牺牲了大量的空间和时间：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.empty()) return nullptr;
        int leftsize = ranges::find(inorder, preorder[0]) - inorder.begin();
        // 直接复制到一个新的 vector 里
        vector<int> preorder_left (preorder.begin()+1, preorder.begin()+1+leftsize);
        vector<int> preorder_right (preorder.begin()+1+leftsize, preorder.end());
        vector<int> inorder_left (inorder.begin(), inorder.begin()+leftsize);
        vector<int> inorder_right (inorder.begin()+leftsize+1, inorder.end());
        TreeNode* left = buildTree(preorder_left, inorder_left);
        TreeNode* right = buildTree(preorder_right, inorder_right);
        return new TreeNode(preorder[0], left, right);
    }
};

现在对 C++ 的认识进一步提高之后，我想出了一种还凑合的写法。我们都知道 C++ 有一个叫 Range 的第三方库，现在已经更新到了 range-v3 。 C++20里这个库已经被合并进了标准库 std 中。 Range 库在处理序列方面有强大的能力。如今的 range-v3 已经支持直接的切片操作（通过 ranges::slice_view 实现），但很遗憾标准库里并没有收录这部分的内容。于是，我转而使用 ranges::subrange 来实现。代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    template<typename _It, typename _Se>
    TreeNode* build_recursive(std::ranges::subrange<_It, _Se> preorder, std::ranges::subrange<_It, _Se> inorder) {
        if (preorder.empty()) {
            return nullptr;
        }
        auto root_val = preorder.front(); // 根结点为前序序列的第一个元素
        auto it = std::ranges::find(inorder, root_val); // 在中序序列中找到根结点
        auto offset = std::ranges::distance(inorder.begin(), it);
        auto root = new TreeNode(root_val);
        // 构造左子树
        root->left = build_recursive(
            std::ranges::subrange{ std::ranges::next(preorder.begin(), 1, preorder.end()), std::ranges::next(preorder.begin(), 1 + offset, preorder.end()) },
            std::ranges::subrange{ inorder.begin(), std::ranges::next(inorder.begin(), offset, inorder.end()) });
        // 构造右子树
        root->right = build_recursive(
            std::ranges::subrange{ std::ranges::next(preorder.begin(), 1 + offset, preorder.end()), preorder.end() },
            std::ranges::subrange{ std::ranges::next(inorder.begin(), 1 + offset, inorder.end()), inorder.end() });
        return root;
    }
    TreeNode* buildTree(std::vector<int>& preorder, std::vector<int>& inorder) {
        return build_recursive(std::ranges::subrange(preorder), std::ranges::subrange(inorder));
    }
};

虽然也用到了辅助函数，但毕竟原函数里只用一行代码去调用辅助函数，也马马虎虎能称得上简洁。辅助函数是预想中的只接受两个序列的形式，内容也与上面描述的伪代码一致。

再来说说通过中序序列与后序序列构造二叉树。按照与上面差不多的思路，中序是“左中右”，后序是“左右中”，同样我们先找到“中”。可以知道根结点就是后序序列的最后一个元素，这时我们拿着最后一个元素去中序序列中找它的位置，找到后同样可以知道左子树的中序序列与右子树的中序序列。我们再用左子树中序序列的长度去切后序序列，得到左子树的后序序列与右子树的后序序列。这时，问题又转化成了它本身。这里不赘述，代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    template<typename _It, typename _Se>
    TreeNode* build_recursive(std::ranges::subrange<_It, _Se> inorder, std::ranges::subrange<_It, _Se> postorder) {
        if (inorder.empty()) {
            return nullptr;
        }
        auto root_val = postorder.back(); // 根结节为后序序列的最后一个元素
        auto it = std::ranges::find(inorder, root_val); // 在中序序列中找到根结点
        auto offset = std::ranges::distance(inorder.begin(), it);
        TreeNode* root = new TreeNode(inorder[offset]);
        // 构造左子树
        root->left = build_recursive(
            std::ranges::subrange{ inorder.begin(), std::ranges::next(inorder.begin(), offset, inorder.end()) },
            std::ranges::subrange{ postorder.begin(), std::ranges::next(postorder.begin(), offset, postorder.end()) });
        // 构造右子树
        root->right = build_recursive(
            std::ranges::subrange{ std::ranges::next(inorder.begin(), offset + 1, inorder.end()), inorder.end() },
            std::ranges::subrange{ std::ranges::next(postorder.begin(), offset, postorder.end()), std::ranges::prev(postorder.end(), 1, postorder.begin()) });
        return root;
    }
    TreeNode* buildTree(std::vector<int>& inorder, std::vector<int>& postorder) {
        return build_recursive(std::ranges::subrange(inorder), std::ranges::subrange(postorder));
    }
};

提交结果：

知识点归纳

std::ranges::subrange 是一个子序列的类，它可以接受一个 range 这时子序列就是给定的序列全部，也可以接受两个迭代器，分别指向子序列的头部和子序列的 尾部下一个位置 （通常叫 setinel ）。它的模板参数 _It 要 model 概念 std::input_or_output_iterator 这个概念规定了一个迭代器要满足的条件。而模板参数 _Se 要 model 概念 std::sentinel_for ，它约束了 sentinel 与迭代器类型之间的关系。

std::ranges::next 与 std::ranges::prev 可以帮助我们安全地移动迭代器，前提是要用它三个参数的重载形式，第一个参数给定要移动的迭代器，第二个参数给定移动的距离，第三个参数给定移动的边界。

参考列表

文章目录

知识点速查

中序与前序或后序联合构造二叉树