合併兩棵二叉樹

Question

public int merge(BNode node, int array[], int i) { 
    if (node == null) 
     return i; 
    //Flatten left subtree 
    i = merge(node.left, array, i); 
    //Get data from the current node 
    array[i] = node.value; 
    //Flatten right subtree 
    i = merge(node.right, array, i + 1); 
    return i; 
} 

我試圖合併兩棵二叉樹並保留BST屬性。 我使用的方法是壓扁樹並將它們存儲在數組中。 上面的函數使我的第一棵樹變平並將它存儲在數組[]中。

我想要一個將rootnode和空數組[]作爲輸入的函數，並將所有節點的扁平樹返回到數組中。

Answer 1

正如你所做的那樣，如果你想合併2個二叉搜索樹，最好的方法是： 1）將樹平鋪到排序列表中。 2）合併列表。 3）將合併列表轉換爲BST。

你可以實現你正在尋找容易這樣的功能：

BinarySearchTree* arrayToTree(int arr[], int start, int end) { 
    if (start > end) return NULL; 
    int mid = start + (end - start)/2; 
    BinarySearchTree *node = new BinarySearchTree(arr[mid]); 
    node->left = arrayToTree(arr, start, mid-1); 
    node->right = arrayToTree(arr, mid+1, end); 
    return node; 
} 

BinarySearchTree* arrayToTree(int arr[], int n) { 
    return arrayToTree(arr, 0, n-1); 
}