1

我正在解决这个问题 - Find PostOrder traversal from Inorder and Preorder traversals of a binary tree。在 GeeksForGeeks 上，我看到了以下解决方案：

// A utility function to search x in arr[] of size n 
static int search(int arr[], int x, int n) 
{ 
    for (int i = 0; i < n; i++) 
        if (arr[i] == x) 
            return i; 
    return -1; 
} 

// Prints postorder traversal from given inorder and preorder traversals 
static void printPostOrder(int in1[], int pre[], int n) 
{ 
    // The first element in pre[] is always root, search it in in[] to find left and right subtrees 
    int root = search(in1, pre[0], n); 

    // If left subtree is not empty, print left subtree 
    if (root != 0) 
        printPostOrder(in1, Arrays.copyOfRange(pre, 1, n), root); 

    // If right subtree is not empty, print right subtree 
    if (root != n - 1) 
        printPostOrder(Arrays.copyOfRange(in1, root+1, n), Arrays.copyOfRange(pre, 1+root, n), n - root - 1); 

    // Print root 
    System.out.print( pre[0] + " "); 
}

现在，我知道在后序中，我们在遍历左右子树后访问该节点，这就是为什么，我可以从 printPostOrder() 方法中的注释推断出首先对左子树进行处理，然后是右子树，然后是节点的正在打印数据。我在纸上画了一些初始的递归调用，它工作正常，但我就是不明白有人怎么能想出这个解决方案？我在为右子树调用 printPostOrder 的语句中特别困惑。谁能帮我理解递归背后的逻辑是什么，以及如何通过正确地可视化它来理解它？

4

1 回答 1

1

设X为根，L和R为左右子树。

    X
  /   \
L      R

然后in[]看起来像

+---------+---+-------------------------+
|    L    | X |            R            |
+---------+---+-------------------------+

看起来pre[]像

+---+---------+-------------------------+
| X |    L    |            R            |
+---+---------+-------------------------+

L和R的块在in和中不会相同pre，它们将被打乱，但主要观察结果是：

  1. L的所有元素在两个数组中都占据一个连续的块。
  2. R的所有元素在两个数组中都占据一个连续的块。
  3. L在两个数组中都在R之前。

int 行在位置root in处root = search(in1, pre[0], n);找到X。一旦我们有了它，我们就知道：in

  1. L具有根元素（X in左侧的所有元素in）。
  2. L出现在位置 0 inin和位置 1 in pre。
  3. R有n - root - 1 个元素（ X in右边的所有元素in）。
  4. R出现在两个数组中的root + 1 位置。

为了清晰和一致，代码可以复制适当的长度和偏移量：

// If left subtree is not empty, print left subtree 
int lsize = root;
if (lsize != 0) 
  printPostOrder(
    Arrays.copyOfRange(in1, 0, lsize),
    Arrays.copyOfRange(pre, 1, lsize),
    lsize);

// If right subtree is not empty, print right subtree 
int rsize = n - root - 1;
if (rsize != 0) 
  printPostOrder(
    Arrays.copyOfRange(in1, root + 1, rsize),
    Arrays.copyOfRange(pre, root + 1, rsize),
    rsize);

为了提高效率，原始代码有时会在起始偏移量不变的情况下重用相同的数组。

顺便说一句，这段代码在O ( n ²) 时间内运行，但在O ( n ) 时间内有更快、更优雅的版本。

于 2019-11-20T15:45:09.973 回答