合并两棵二叉树

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