Convert a BST to a sorted circular doubly-linked list in-place. Think of the left and right pointers as synonymous to the previous and next pointers in a doubly-linked list.
If the problem statement is still not clear to you, below is a pictorial representation of what you need to do:
I originally read this interesting problem here: The Great Tree-List Recursion Problem.
Hint:
Think of in-order traversal. How do you ensure that the last element’s right pointer points back to the first element?
Solution:
When I first see this problem, my first thought was in-order traversal. Couldn’t we modify the nodes’ left and right pointers as we do an in-order traversal of the tree? However, we have to beware not to modify the pointers and accessing it at a later time.
As we traverse the tree in-order, we could safely modify a node’s left pointer to point to the previously traversed node as we never use it once we reach a node. We would also need to modify the previously traversed node’s right pointer to point to the current node. Note: The previously traversed node meant here is not its parent node. It is the node’s previous smaller element.
Easy approach, right? But wait, we are still missing two more steps. First, we did not assign the list’s head pointer. Second, the last element’s right pointer does not point to the first element (similar to the first element’s left pointer).
How do we solve this? My approach is pretty easy: Just update the current node’s right pointer to point back to the head and the head’s left pointer to point to current node in each recursive call. As the recursion ends, the list’s head and tail would be automagically updated with the correct pointers. Don’t forget to check for this special case: A list with only one element should have its left and right pointers both pointing back to itself.
Do you think this approach works? I bet it did! The run time complexity for this solution is O(N) since we are essentially doing a modified in-order traversal. It does have some extra assignments in each recursive call though. But overall I am quite satisfied with this approach because it is intuitive and easy to follow. Besides, we are adapting an existing algorithm (in-order traversal) to solve this problem, isn’t this just neat?
private TreeNode prev; private TreeNode head; public TreeNode bstToSortedDLL(TreeNode node) { if(node == null) return null; bstToSortedDLL(node.left); node.left = prev; if(prev != null) { prev.right = node; } else { head = node; } prev = node; TreeNode right = node.right; head.left = node; node.right = head; bstToSortedDLL(right); return head; }
Reference:
http://articles.leetcode.com/2010/11/convert-binary-search-tree-bst-to.html
相关推荐
BST-BMP180-DS000-07.pdf英文资料
The BME280 supports a full suite of operating modes which provides the flexibility to optimize the device for power consumption, resolution and filter performance." Applications - Context awareness,...
BST-BMP280-DS001-18手册.pdf
将bst文件放到MiKTeX的bst文件夹下自己新建的gbt7714-2005文件下,1)作者名称如 KERNER B S 的样式 GBT7714-2005NLang.bst 2)作者名称如 KERNER B S 的样式 GBT7714-2005NLang_UP.bst 3)作者名称如 Kerner B S 的...
该资源为国标参考文献的bst样式文件,GBT7714-2005NLang.bst样式文件。可以在论文参考文献排版时使用
ST digital pressure sensor BMP280 spec
大气压传感器BMP085,可以根据大气压值来判断高度,可以用于对于高度的定位以及平面定位转成3D定位。
BOSH bmp189 气体传感器说明文档,希望对初学者有用
舵机供电模块超声波模块供电口舵机模块电机模块红外检测模块检测提示模块电源提示灯亚博 BST-V51 智能小车底板电路原理图。
bmi088 芯片手册
BMP280手册
环境传感器手册
环境传感器手册
51代码,51单片机所有代码,定时器、数码管、iIC、led、数码管
bmi160datasheet, 和设计手册
This is BMP280 data sheet, you can reference it.
AVL和红黑树性能对比,有详细的测试数据。AVL和红黑树都是平衡树。...a in-order doubly linked list is advantageous when traversal is very common; and right-threaded nodes perform poorly.
加载BST薄膜的寄生贴片功能研究,朱典全,童玲,借助于钛酸锶钡BST(Barium Strontium Titanate)铁电薄膜的介电可调性,在一单元微带贴片天线适当位置处加载BST薄膜,研究了BST薄膜介电常��
* [Linked List](https://github.com/kamyu104/LeetCode#linked-list) * [Stack](https://github.com/kamyu104/LeetCode#stack) * [Queue](https://github.com/kamyu104/LeetCode#queue) * [Heap]...
视频,源代码,光盘配套一切资料