给定一个 BST，打印不同节点对的所有可能组合

Question

假设您有以下 BST：

  4
 /  \
2    8

使用以下 C 结构实现：

typedef struct node{
    int data;
    struct node* left;
    struct node* right;
}node;

输出将是：

(4,2)
(4,8)
(2,4)
(2,8)
(8,4)
(8,2)

这个算法如何实现？

是否有可能以在运行时提供比 O(n^2 - n) 更好的正确输出的方式实现算法 ?

Answer 1

我找到了解决方案：

And is it possible to implement the algorithm in such a way that gives the correct output in a runtime better than O(n^2 - n) ?

不，运行时间不可能比 O(n^2 - n).

How can this algorithm be implemented?

void printPairsHelper(node* root, node* temp){
    if (!root) return;
 
    if (root != temp) printf("%d, %d\n", root->data, temp->data);
 
    printPairsHelper(root->left, temp);
    printPairsHelper(root->right, temp);
}

void printPairs(node* root, node* curr){
    if (!curr) return;
 
    printPairsHelper(root, curr);
 
    printPairs(root, curr->left);
    printPairs(root, curr->right);
}

用法：

//Declare the BST
node* root = NULL;

//Add some nodes to the BST

//...

//Call the function
printPairs(root, root);

给定一个 BST，打印不同节点对的所有可能组合

Given a BST, print all the possible combinations of differents nodes pairs

c

algorithm

binary-search-tree

combinations

permutation