简历：The Google Resume: How to Prepare for a Career and Land a Job at Apple, Microsoft, Google, or any Top Tech Company
算法学习书籍：Introduction to Algorithms
编程珠玑：Programming Pearls (2nd Edition)
C++ 学习：The C++ Programming Language, 4th Edition
经典操作系统书籍，龙书：Operating System Concepts
创业：The Start-up of You: Adapt to the Future, Invest in Yourself, and Transform Your Career
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?
confused what
» Solve this problem"{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.这道题思路很巧妙。刚开始我想穷举所有的情况，然后swap two nodes，后来发现这样做太不现实了。并且code很冗长。在网上看到说用in-order，刚开始没想到关in-order啥事儿。后来想到，因为是binary search tree,所以 in-order traverse得到的array应该是一个递增序列，这样我们就可以把这棵树看作一个array，然后只是其中两个点儿被swap了，找到这两个点，再swap回来就好，这样就不用考虑那些各种情况了。
用2个pointer，一个是pre，一个是current，若是current->val<pre->val, 那么纪录下cur, 遇到下一个再纪录下cur。以免遇到只有两个点儿的情况，要判断一下要不要纪录pre。
然后就是in-order traverse的变体。
还有一个分析得比较多的解法，可以看看 http://fisherlei.blogspot.com/2012/12/leetcode-recover-binary-search-tree.html
if(!n1)
ReplyDeleten1 = prev;
这个很巧妙， 否则很难找到第一个错误的位置
一直不理解这个constant space 怎么理解，递归不是constant space啊
ReplyDelete这个答案并不是constant space, 可以看一下 http://fisherlei.blogspot.com/2012/12/leetcode-recover-binary-search-tree.html
Delete还挺麻烦的
"用2个pointer，一个是pre，一个是current，若是current->valval, 那么纪录下cur, 遇到下一个再纪录下cur。以免遇到只有两个点儿的情况，要判断一下要不要纪录pre。"
ReplyDelete若是current.val< pre.val （第一个错误点）应该记录下pre吧 ， 第二个错误才是纪录cur的
This comment has been removed by the author.
ReplyDelete