3

这是一个面试题。

给出了一个二叉搜索树，并且两个节点的值已经交换。问题是如何在树的一次遍历中找到节点和交换的值？

我试图使用下面的代码解决这个问题，但我无法停止递归，所以我遇到了分段错误。帮助我如何停止递归。

#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;

}
4

5 回答 5

7

使用中序遍历走到树。通过使用它，您将对所有元素进行排序，并交换一个大于周围元素的元素。

例如考虑下面的二叉树

          _  20  _
         /         \
      15             30
     /   \         /   \ 
   10    17      25     33
  / |   /  \    /  \    |  \
9  16  12  18  22  26  31  34

首先，我们将其线性化为一个数组，我们得到

9 10 16 15 12 17 18 20 22 25 26 30 31 33 34

现在您可以注意到 16 大于其周围的元素，而 12 则小于它们。这立即告诉我们交换了 12 和 16。

于 2012-09-04T11:12:34.603 回答
2

以下函数通过在收紧边界的同时递归地迭代左右子树来验证树是否为 BST。

我相信可以通过修改它来实现上述任务

  1. 不是返回false，而是返回temp 即指向使树无法成为BST 的节点的指针。
  2. 会有两个这样的实例同时给出交换的值。

编辑：我们需要区分返回 true 的递归函数和指向被交换节点的指针

这假设只有问题定义中提到的两个这样的值

bool validate_bst(tnode *temp, int min, int max)
{
        if(temp == NULL)
                return true;

        if(temp->data > min && temp->data < max)
        {
                if( validate_bst(temp->left, min, temp->data) && 
                    validate_bst(temp->right, temp->data, max) )
                        return true;
        }

        return false;
}

主要会像这样调用上面的api

   validate_bst(root, -1, 100); // Basically we pass -1 as min and 100 as max in
                                     // this instance
于 2012-09-04T12:05:24.157 回答
1

我们可以在 O(n) 时间内解决这个问题，并且只需遍历给定的 BST。由于 BST 的中序遍历始终是排序数组，因此问题可以简化为交换排序数组的两个元素的问题。我们需要处理两种情况：

      6 
    /  \ 
   10    2 
  / \   / \ 
 1   3 7  12

1.交换的节点在BST的中序遍历中不相邻。

例如，节点 10 和 2 在 {1 10 3 6 7 2 12} 中交换。给定树的中序遍历是 1 10 3 6 7 2 12

如果我们仔细观察，在中序遍历过程中，我们发现节点 3 比之前访问的节点 10 小。这里保存节点 10（上一个节点）的上下文。再次，我们发现节点 2 比之前的节点 7 小。这一次，我们保存节点 2（当前节点）的上下文。最后交换两个节点的值。

2.交换的节点在BST的中序遍历中相邻。

      6 
    /  \ 
   10    8 
  / \   / \ 
 1   3 7  12

例如，节点 10 和 2 在 {1 10 3 6 7 8 12} 中交换。给定树的中序遍历是 1 10 3 6 7 8 12 与案例 #1 不同，这里仅存在一个节点值小于前一个节点值的点。例如，节点 10 小于节点 36。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void recoverTreeUtil(TreeNode *root, TreeNode **first, TreeNode **middle, TreeNode **last, TreeNode **prev) {
        if (root) {
            recoverTreeUtil(root->left, first, middle, last, prev);
            if (*prev && (*prev)->val > root->val) {
                if (!(*first)) {
                    *first = *prev;
                    *middle = root;
                } else *last = root;
            }
            *prev = root;
            recoverTreeUtil(root->right, first, middle, last, prev);
        }
    }
    void recoverTree(TreeNode* root) {
        TreeNode *first, *middle, *last, *prev;
        first = middle = last = prev = nullptr;
        recoverTreeUtil(root, &first, &middle, &last, &prev);
        if (first && last) swap(first->val, last->val);
        else if (first && middle) swap(first->val, middle->val);
    }
};
于 2019-12-04T16:45:41.290 回答
0

我在 Geeksforgeeks.com 上找到了这个问题的另一个解决方案 ........你们可以查看这个线程以获得对以下代码的更多解释http://www.geeksforgeeks.org/archives/ 23616

// Two nodes in the BST's swapped, correct the BST.
#include <stdio.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, *right;
};

// A utility function to swap two integers
void swap( int* a, int* b )
{
int t = *a;
*a = *b;
*b = t;
}

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

// This function does inorder traversal to find out the two swapped nodes.
// It sets three pointers, first, middle and last.  If the swapped nodes are
// adjacent to each other, then first and middle contain the resultant nodes
// Else, first and last contain the resultant nodes
void correctBSTUtil( struct node* root, struct node** first,
                 struct node** middle, struct node** last,
                 struct node** prev )
{
if( root )
{
    // Recur for the left subtree
    correctBSTUtil( root->left, first, middle, last, prev );

    // If this node is smaller than the previous node, it's violating
    // the BST rule.
    if (*prev && root->data < (*prev)->data)
    {
        // If this is first violation, mark these two nodes as
        // 'first' and 'middle'
        if ( !*first )
        {
            *first = *prev;
            *middle = root;
        }

        // If this is second violation, mark this node as last
        else
            *last = root;
    }

    // Mark this node as previous
    *prev = root;

    // Recur for the right subtree
    correctBSTUtil( root->right, first, middle, last, prev );
}
}

// A function to fix a given BST where two nodes are swapped.  This
// function uses correctBSTUtil() to find out two nodes and swaps the
// nodes to fix the BST
void correctBST( struct node* root )
{
// Initialize pointers needed for correctBSTUtil()
struct node *first, *middle, *last, *prev;
first = middle = last = prev = NULL;

// Set the poiters to find out two nodes
correctBSTUtil( root, &first, &middle, &last, &prev );

// Fix (or correct) the tree
if( first && last )
    swap( &(first->data), &(last->data) );
else if( first && middle ) // Adjacent nodes swapped
    swap( &(first->data), &(middle->data) );

// else nodes have not been swapped, passed tree is really BST.
}

/* A utility function to print Inoder traversal */
void printInorder(struct node* node)
{
if (node == NULL)
    return;
printInorder(node->left);
printf("%d ", node->data);
printInorder(node->right);
}

/* Driver program to test above functions*/
int main()
{
/*   6
    /  \
   10    2
  / \   / \
 1   3 7  12
 10 and 2 are swapped
*/

struct node *root = newNode(6);
root->left        = newNode(10);
root->right       = newNode(2);
root->left->left  = newNode(1);
root->left->right = newNode(3);
root->right->right = newNode(12);
root->right->left = newNode(7);

printf("Inorder Traversal of the original tree \n");
printInorder(root);

correctBST(root);

printf("\nInorder Traversal of the fixed tree \n");
printInorder(root);

return 0;
}
Output:

 Inorder Traversal of the original tree
 1 10 3 6 7 2 12
 Inorder Traversal of the fixed tree
 1 2 3 6 7 10 12
 Time Complexity: O(n)

更多测试用例请参考此链接http://ideone.com/uNlPx

于 2012-09-14T05:14:34.650 回答
-1

我的 C++ 解决方案：

struct node *correctBST( struct node* root )
{
//add code here.
    if(!root)return root;
    struct node* r = root;
    stack<struct node*>st;
   // cout<<"1"<<endl;
    struct node* first = NULL;
    struct node* middle = NULL;
    struct node* last = NULL;
    struct node* prev = NULL; 
    while(root  || !st.empty()){
        while(root){
            st.push(root);
            root = root->left;
        }
        root = st.top();
        st.pop();
        if(prev && prev->data > root->data){
            if(!first){
                first = prev;
                middle = root;
            }
            else{
                last = root;
            }
        }
        prev = root;
        root = root->right;
    }
    if(first && last){
        swap(first->data,last->data);
    }
    else{
        swap(first->data,middle->data);
    }
    return r;
}
于 2018-01-14T13:32:25.657 回答