Java/C/C++ :find leaf of the shortest path of a binary tree without reconstructing tree (help with recursion)

Question

我有这两个二叉树序列(不是 BSD):
顺序:3 2 1 4 5 7 6
后序:3 1 2 5 6 7 4

我们知道postOrder中的最后一个元素是根，所以我们把根定位在inOrder序列上，这样 segmentation :
- 根左侧的所有元素都转到左子树
- 根右侧的所有元素都进入右子树 此外，它们在树中出现的顺序由 postOrder 给出。

对于这个例子: 4 = 根

左子树(有序):3 2 1 右子树(有序):5 7 6
左子树(后序):3 1 2 右子树(后序):5 6 7

我们递归地做同样的事情......所以，我认为重建的树是:

              4
         2         7
      3     1    5   6

我只想返回导致最短路径(总和)的叶子；我不需要重建树然后遍历它并做最短路径。我只需要引导我达到最小总和的叶子。 在这种情况下，我有 4 条可能的路径:4+2+3=9 || 4+2+1 = 7 || 4+7+5 = 16 || 4+7+6 = 17，少的是7，必须还叶1。

我觉得这个算法很简单，但是我很难为它写递归代码......

有人可以帮助菜鸟吗？ C、Java、C++ 或 Python ...我不介意

Answer 1

如果您对一般二叉树进行中序遍历和后序遍历，如果您可以有重复的值，它们甚至不会唯一地定义树，例如后序和中序的序列 [1,1,1] 可以是以下树之一:

    1      1
   1 1      1
             1

最小和路径左边是2的和，右边是3的和。

因此假设所有值都是不同的。

假设你有一个后序遍历列表 [x1,x2,...,xn] 和中序遍历列表 [y1,...,yk,...,yn] 使得 xn==yk .因为 xn 是树的根，所以您现在知道 [y1,...,yk-1] 是左子树，而 [yk+1,...,yn] 是右子树。然后左子树也用[x1,...,xk-1]表示，因为左子树的大小显然是常数，所以你也可以将后序遍历列表划分为xk-1和xk。

例如，这是一个没有任何特定顺序的非平衡二叉树:

     5
   3   6
  9 2   1
       4

中序遍历为[9,3,2,5,6,4,1]，后序为[9,2,3,4,1,6,5]。

树将像这样递归构造:取后序遍历的最后一个元素 (5)；按顺序划分为 [9,3,2] 和 [6,4,1](在元素 5 的位置划分)；因此，仅基于现在已知的子树大小，后序遍历列表被拆分为 [9,2,3] 和 [4,1,6]。然后递归继续；让我们看看 [6,4,1] 树，因为它不平衡:

根是6；在中序 [6,4,1] 中，左子树为空，右子树为 [4,1]，因此从后序列表 [4,1,6] 中，您将 [] 作为左子树subtree 和 [4,1] 作为右子树；从那里你得到根节点 1，你发现 [4] 是左子树；从中得到形状

  6
   1
  4

根据需要。

现在因为您的树没有排序、平衡等，您可以尝试编写递归代码来处理您的查询。这是在 C++ 中:

const int size = 7; /* Size of the tree */

/* Given arrays */
int post_order[size] = { 3 , 1 , 2 , 5 , 6 , 7 , 4 };
int in_order[size] = { 3 , 2 , 1 , 4 , 5 , 7 , 6 };

/* Variables updated during recursion */
int min_sum = 99999999; /* not initialized */
int best_leaf = -1; /* not initialized */

/* Recursive descent */
/* prb = post-order range begin, irb = in-order range begin, etc. */
void min_sum_leaf(int acc, int prb, int irb, int len) {
  if (len == 0) return; /* empty subtree */
  if (len == 1) { /* leaf */
    int sum = acc + in_order[irb];
    if (sum<min_sum) { min_sum = sum; best_leaf = in_order[irb]; }
    return;
  }
  /* non-leaf */
  int subtree_root = post_order[prb + len - 1];
  /* find the size of the left subtree */
  int i;
  for (i=0;i<len;i++) {
    if (in_order[irb + i] == subtree_root) break;
  }
  /* Now i is the length of the left subtree, len - i - 1 of the right */
  min_sum_leaf(acc + subtree_root, prb, irb, i);
  min_sum_leaf(acc + subtree_root, prb + i, irb + i + 1, len - i - 1);
}

/* Driver */
int find_min_sum_leaf() {
  min_sum = 99999999; best_leaf = -1;
  min_sum_leaf(0, 0, 0, size);
  return best_leaf;
}

注意:我没有编译或运行算法，但逻辑应该在那里!