从中序遍历打印所有二叉树

Question

在面试中遇到了这个问题。给定一个二叉树的中序遍历，输出所有可能的二叉树。

初始想法：

如果说数组中只有2个元素，比如2,1。那么可能的树有两种：

              2 
               \
                1     
    1
   /
   2  

如果有三个元素，分别为2、1和4，则有5种可能的树形结构。

 2               1            4           2            4
  \             / \          /             \          /
   1           2   4        1               4        2
    \                      /               /          \
     4                    2               1            1

基本上，如果我们有n个元素，那么我们就有n-1个分支（子节点、/或）。我们可以以任何顺序排列这n-1个分支。 对于n=3，n-1=2。所以我们有2个分支。 我们可以用以下方式排列这2个分支：

  /     \         \           /         /\
 /       \        /           \

最初的尝试：

struct  node *findTree(int *A,int l,int h)
{
    node *root = NULL;
    if(h < l)
            return NULL;
    for(int i=l;i<h;i++)
    {
            root = newNode(A[i]);
            root->left = findTree(A,l,i-1);
            root->right = findTree(A,i+1,h);
            printTree(root);
            cout<<endl;
    }

}

- Deepti Jain

---

在你的示例中，使用(1, 2, 4)，最后一个示例应该是从上到下的4-1-2吗？ - That Chuck Guy

@ChuckBlumreich 数组是2,1,4。我猜数字是正确的。 - Deepti Jain

有趣的问题，但我不确定你的图表。 我将“按顺序”遍历解释为“访问左子节点，访问节点，访问右子节点”（与先序“访问N，访问L，访问R”和后序“访问L，访问R，访问N”相对比）。 如果是这样，那么对于一对(2,1)的两棵树来说，它们的结构应该是(根=2，右子节点=1)如图所示和(左子节点=2，根=1)，而这不是你绘制的图表。 我对更复杂的图表也有类似的担忧，但我可能完全误解了某些东西。 - Jonathan Leffler

我同意@Jonathan的观点，这些图表是不正确的。 - Daniel Fischer

同意，是个愚蠢的错误。现在已经更正了图示。 - Deepti Jain

Answer 1

这个问题可以很好地分解成子问题。给定中序遍历后，选择根节点后，我们知道在它之前的所有节点都是左子树，在它之后的所有节点都是右子树（可能为空）。

因此，为了枚举所有可能的树，我们只需尝试所有可能的根值，并递归解决左右子树（这样的树的数量增长非常快！）

Antonakos 提供了一段代码来实现这一点，但该解决方案可能会使用比所需更多的内存。可以通过向递归添加更多状态来解决这个问题，这样它就不必保存左右答案列表并在最后将它们组合起来，而是嵌套这些过程，并在找到每棵树时打印它。

- Sumudu Fernando

Answer 2

我会编写一个函数来构建树，另一个函数用于打印它们。

树的构建步骤如下：

#include <vector>
#include <iostream>
#include <boost/foreach.hpp>

struct Tree {
    int value;
    Tree* left;
    Tree* right;

    Tree(int value, Tree* left, Tree* right) :
        value(value), left(left), right(right) {}
};

typedef std::vector<Tree*> Seq;

Seq all_trees(const std::vector<int>& xs, int from, int to)
{
    Seq result;
    if (from >= to) result.push_back(0);
    else {
        for (int i = from; i < to; i++) {
            const Seq left = all_trees(xs, from, i);
            const Seq right = all_trees(xs, i + 1, to);
            BOOST_FOREACH(Tree* tl, left) {
                BOOST_FOREACH(Tree* tr, right) {
                    result.push_back(new Tree(xs[i], tl,  tr));
                }
            }
        }
    }
    return result;
}

Seq all_trees(const std::vector<int>& xs)
{
    return all_trees(xs, 0, (int)xs.size());
}

观察到对于根值，可以从根值左侧和右侧的值构建多个树。这些左侧和右侧树的所有组合都包括在内。

编写漂亮打印程序留作练习（一项枯燥的任务），但我们可以测试该函数确实构造了预期数量的树：

int main()
{
    const std::vector<int> xs(3, 0); // 3 values gives 5 trees.
    const Seq result = all_trees(xs);
    std::cout << "Number of trees: " << result.size() << "\n";
}

- antonakos