これはインタビューの質問です。
二分探索木が与えられ、2 つのノードの値が交換されています。問題は、ツリーの 1 回のトラバーサルでノードとスワップされた値の両方を見つける方法です。
以下のコードを使用してこれを解決しようとしましたが、再帰を停止できないため、セグメンテーション違反が発生しています。再帰を止める方法を教えてください。
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <stdlib.h>
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
void modifiedInorder(struct node *root, struct node **nextNode)
{
static int nextdata=INT_MAX;
if(root)
{
modifiedInorder(root->right, nextNode);
if(root->data > nextdata)
return;
*nextNode = root;
nextdata = root->data;
modifiedInorder(root->left, nextNode);
}
}
void inorder(struct node *root, struct node *copyroot, struct node **prevNode)
{
static int prevdata = INT_MIN;
if(root)
{
inorder(root->left, copyroot, prevNode);
if(root->data < prevdata)
{
struct node *nextNode = NULL;
modifiedInorder(copyroot, &nextNode);
int data = nextNode->data;
nextNode->data = (*prevNode)->data;
(*prevNode)->data = data;
return;
}
*prevNode = root;
prevdata = root->data;
inorder(root->right, copyroot, prevNode);
}
}
/* Given a binary tree, print its nodes in inorder*/
void printInorder(struct node* node)
{
if (node == NULL)
return;
/* first recur on left child */
printInorder(node->left);
/* then print the data of node */
printf("%d ", node->data);
/* now recur on right child */
printInorder(node->right);
}
int main()
{
/* 4
/ \
2 3
/ \
1 5
*/
struct node *root = newNode(1); // newNode will return a node.
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
printf("Inorder Traversal of the original tree\n ");
printInorder(root);
struct node *prevNode=NULL;
inorder(root, root, &prevNode);
printf("\nInorder Traversal of the fixed tree \n");
printInorder(root);
return 0;
}