注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex99 Recover Binary Search Tree  

2015-05-25 22:24:52|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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?

我已经想到了要用类似滑动窗口的方式来对树进行遍历,不过居然自己没有写出来还是看的别人的代码,真是很冤!!! 
二叉搜索树,中序遍历后是递增的序列,一旦有两个错误交换了,说明有一个波峰还有一个波谷,同时还有一种特殊情况就是波峰和波谷是连着的,因为可能是两个“相邻连续”元素交换了。画一个图就能看出来了。代码中维护一个pre节点,每次遍历的时候当前节点的前一个节点放在pre节点中,这样好找错误的p1和p2。在遍历的时候也要做中序遍历,需要先确定pre节点,当时就是被这点给弄迷糊了,没有写出来。

TreeNode* Node(TreeNode* current, int *index, int*value, int nums)
{
//这个函数用来创建树 创建方式是先序遍历
current = (TreeNode*)malloc(sizeof(TreeNode));
if (value[index[0]] != -1)
{
current->val = value[index[0]];
current->left = NULL;
index[0]++;
if (index[0] < nums)
{
current->left = Node(current->left, index, value, nums);
}
current->right = NULL;
if (index[0] < nums)
{
current->right = Node(current->right, index, value, nums);
}
}
else
{
current = NULL;
index[0]++;
}
return current;
}

/*
*平衡树的特性 : root->key 大于 left->key
* root->key 小于 right->key
* 并且其子树也是平衡树
*/
//能想到要遍历记录三个节点,依次滑动,但是写的时候居然没有自己写出来!!!
void traverse(struct TreeNode* current,struct TreeNode **p1, struct TreeNode**p2, struct TreeNode**pre)
{
//中序遍历二叉搜索树,违反规则的就是两个mistake
if (current == NULL) return;

traverse(current->left,p1, p2,pre);
//这里有了current,先给pre赋值
if (pre[0] != NULL&&pre[0]->val > current->val)
{
//找到违反规则的了 前面的节点一定要比后面的小
//可以画一个图看看,第一次违反的时候一定是一个波峰,违反的节点是波峰
//也就是pre

//第二次违反的时候是一个波谷
//而违反的节点就是current,所以else语句后面是给p2赋值

//那为什么在if判断里面第一次遇到p1和p2都赋值了?
//这是因为两个交换的点可能是相邻的,而p1是pre,p2就是current
//刚好这个波峰波谷的形式和上面两次违反规则的分析是一致的
if (p1[0] == NULL)
{
p1[0] = pre[0];
p2[0] = current;
}
else
{
p2[0] = current;
}
}
pre[0] = current; //窗口滑动,current给pre
traverse(current->right, p1, p2, pre); //遍历右子树

}
void recoverTree(struct TreeNode* root) {
struct TreeNode*p1, *p2, *pre;
int tmp;
p1 = NULL;
p2 = NULL;
pre = NULL;
traverse(root, &p1, &p2, &pre);
//最后交换两个点
if (p1 != NULL&&p2 != NULL)
{
tmp = p1->val;
p1->val = p2->val;
p2->val = tmp;
}
}


  评论这张
 
阅读(8)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017