如何将完全二叉树数组转换为中序遍历数组？附题背景与代码

Hey there! Let's fix your code and get that in-order traversal array right.

First, let's break down the issues in your current implementation:

• Pass-by-value problem with destIndex: In Java, primitive types like int are passed by value. When you increment destIndex++ inside the recursive call, that change doesn't propagate back to the parent call. This means your dest array will end up with incorrect values or overwrites.
• Incorrect child node existence check: Your condition leftIndex < source.length misses cases where the left child index equals the array length (since node positions go from 1 to N, where N is the number of nodes and the length of your source array). For example, if N=4, the left child of position 2 is position 4, which exists but 4 < 4 evaluates to false.

Fix 1: Use a mutable index holder (array) #

Since arrays are reference types in Java, we can use a single-element array to hold the destIndex value—changes to this value will be visible across all recursive calls. Here's the corrected code:

static void inOrderArr(int[] destIndex, int index, int[] source, int[] dest) {
    int leftIndex = index * 2;
    int rightIndex = index * 2 + 1;
    
    // Traverse left subtree first if it exists
    if (leftIndex <= source.length) {
        inOrderArr(destIndex, leftIndex, source, dest);
    }
    
    // Fill current node's value into dest array, then increment index
    dest[destIndex[0]] = source[index - 1];
    destIndex[0]++;
    
    // Traverse right subtree next if it exists
    if (rightIndex <= source.length) {
        inOrderArr(destIndex, rightIndex, source, dest);
    }
}

How to call this:

int[] source = {10, 20, 30, 40}; // Corresponding to a[1]=10, a[2]=20, a[3]=30, a[4]=40
int[] dest = new int[source.length];
int[] destIndex = {0}; // Mutable holder for the destination index
inOrderArr(destIndex, 1, source, dest);
// dest now holds the in-order traversal: [40, 20, 10, 30]

Fix 2: Return the updated index from recursion #

Another approach is to have the recursive method return the updated destIndex after processing the current subtree. This avoids needing a mutable holder:

static int inOrderArr(int index, int[] source, int[] dest, int destIndex) {
    int leftIndex = index * 2;
    int rightIndex = index * 2 + 1;
    
    // Update index after traversing left subtree
    if (leftIndex <= source.length) {
        destIndex = inOrderArr(leftIndex, source, dest, destIndex);
    }
    
    // Fill current node and increment index
    dest[destIndex] = source[index - 1];
    destIndex++;
    
    // Update index after traversing right subtree
    if (rightIndex <= source.length) {
        destIndex = inOrderArr(rightIndex, source, dest, destIndex);
    }
    
    // Return the updated index to the parent call
    return destIndex;
}

How to call this:

int[] source = {10, 20, 30, 40};
int[] dest = new int[source.length];
inOrderArr(1, source, dest, 0);
// dest will be [40, 20, 10, 30], same as before

Key Notes: #

• We use source[index - 1] because your source array stores the tree's a[1] at index 0, a[2] at index 1, etc.
• The condition leftIndex <= source.length correctly checks if the left child exists (since node positions range from 1 to source.length).

Once you have the in-order traversal array, you can proceed to calculate the minimum number of swaps needed to convert it into a sorted array (since a valid BST's in-order traversal is sorted). That's a standard problem—you can map each element to its target position in the sorted array and count cycles to find the minimum swaps.

内容的提问来源于stack exchange，提问作者Ramesh Papaganti