从遍历遍历打印所有二叉树 [英] printing all binary trees from inorder traversal

问题描述

在面试中遇到这个问题。
给定二叉树的顺序遍历。打印所有可能的二叉树。

Came across this question in an interview. Given inorder traversal of a binary tree. Print all the possible binary trees from it.

初始想法：

如果说我们只有2个元素数组。说2,1。
然后两个可能的树是

If say we have only 2 elements in the array. Say 2,1. Then two possible trees are

              2 
               \
                1     
    1
   /
   2  

如果3个元素说，2,1,4。然后我们有5个可能的树。

If 3 elements Say, 2,1,4. Then we have 5 possible trees.

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

b $ b

因此，基本上如果我们有n个元素，那么我们有n-1个分支（子元素，/或）。
我们可以按任何顺序排列这些n-1分支。
对于n = 3，n-1 = 2。因此，我们有2个分支。
我们可以通过以下方式安排两个分支：

So, basically if we have n elements, then we have n-1 branches (childs, / or ). We can arrange these n-1 branches in any order. For n=3, n-1 = 2. So, we have 2 branches. We can arrange the 2 branches in these ways:

  /     \         \           /         /\
 /       \        /           \

初始尝试次数：

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;
    }

}

推荐答案

这个问题很好地分解成子问题。给定一个顺序遍历，在选择一个根之后，我们知道之前的所有是左子树和后面的子节点是正确的子树（可能是空的）。

This problem breaks down quite nicely into subproblems. Given an inorder traversal, after choosing a root we know that everything before that is the left subtree and everthing after is the right subtree (either is possibly empty).

枚举所有可能的树，我们只是尝试根的所有可能的值，并递归地求解左和右侧子树（虽然这样的树的数量相当快！）

So to enumerate all possible trees, we just try all possible values for the root and recursively solve for the left & right subtrees (the number of such trees grows quite quickly though!)

antonakos提供的代码显示了如何做到这一点，虽然这个解决方案可能使用更多的内存。这可以通过向递归添加更多的状态来解决，因此它不必保存左和右的答案的列表。右结合在一起;而是嵌套这些进程，并打印每个树，因为它是找到的。

antonakos provided code that shows how to do this, though that solution may use more memory than desirable. That could be addressed by adding more state to the recursion so it doesn't have to save lists of the answers for the left & right and combine them at the end; instead nesting these processes, and printing each tree as it is found.

这篇关于从遍历遍历打印所有二叉树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！