首页 > 剑指offer > LeetCode-Recover Binary Search Tree[二叉树]
2014
06-13

LeetCode-Recover Binary Search Tree[二叉树]

修复二分查找树,常见的面试题

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

 

有一个二分查找二叉树,交换了其中任意两个节点,要求恢复此二叉树。要求时间复杂度为 O(n),时间复杂度O(1)。

直接在树中找这两个节点不太容易,可以把二分查找树看成一个已经排序的数组,以为二分查找树的中序遍历即为升序排序。

对于一个已经排序的数组,交换任意两个元素后很容易恢复,例如对于

2 3 4 5 6 7 8
交换 3 和 6
2 6 4 5 3 7 8
恢复的话遍历一边即可,分别用两个指针记录第一个和最后一个破坏排序的元素。

完整的代码如下:

#include <iostream>
using namespace std;

/* 二叉树节点 */
struct TreeNode
{
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* newNode(int data)
{
    struct TreeNode * node = new struct TreeNode;
    node->val = data;
    node->left = NULL;
    node->right = NULL;
    return(node);
}

class Solution {
public:
	TreeNode * pre, * first, * last;
    void recoverTree(TreeNode *root) {
    	pre = first = last = NULL;
    	inOrder(root);
    	swap(first->val, last->val);
    }
    void inOrder(TreeNode * root){
    	if(!root) return;
    	inOrder(root->left);
    	        if(pre&& pre->val > root->val)
    	        {
    	        	if(first == NULL)//first必须为最左边的
    	        		first = pre;
    	        	last = root;
    	        }
    	        pre=root;
    	        inOrder(root->right);
    }

};

void inOrderTra(TreeNode * root){
	if(root == NULL) return;
	inOrderTra(root->left);
	cout << root->val << " ";
	inOrderTra(root->right);
}

//测试
int main()
{
    /*  创建以下的树
            6
          /   \
        4      7
      /  \    /
    3     5  8
   /
  2

  */
  struct TreeNode *root = newNode(6);
  root->left        = newNode(4);
  root->right       = newNode(8);
  root->left->left  = newNode(3);
  root->left->left->left  = newNode(2);
  root->left->right = newNode(5);
  root->right->left = newNode(7);

  //中序遍历
  inOrderTra(root);
  cout << endl;

  //交换3和6
  root->left->left->val = 6;
  root->val = 3;
  //中序遍历
  inOrderTra(root);
   cout << endl;

  Solution s;
  s.recoverTree(root);
  //中序遍历
  inOrderTra(root);
  cout << endl;
  return 0;
}

  1. /*
    * =====================================================================================
    *
    * Filename: 1366.cc
    *
    * Description:
    *
    * Version: 1.0
    * Created: 2014年01月06日 14时52分14秒
    * Revision: none
    * Compiler: gcc
    *
    * Author: Wenxian Ni (Hello World~), [email protected]
    * Organization: AMS/ICT
    *
    * =====================================================================================
    */

    #include
    #include

    using namespace std;

    int main()
    {
    stack st;
    int n,i,j;
    int test;
    int a[100001];
    int b[100001];
    while(cin>>n)
    {
    for(i=1;i>a[i];
    for(i=1;i>b[i];
    //st.clear();
    while(!st.empty())
    st.pop();
    i = 1;
    j = 1;

    while(in)
    break;
    }
    while(!st.empty()&&st.top()==b[j])
    {
    st.pop();
    j++;
    }
    }
    if(st.empty())
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
    }
    return 0;
    }