https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。
为了让您更好地理解问题,以下面的二叉搜索树为例:
我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表,第一个节点的前驱是最后一个节点,最后一个节点的后继是第一个节点。
下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。
特别地,我们希望可以就地完成转换操作。当转化完成以后,树中节点的左指针需要指向前驱,树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
中序遍历
每次都记录上前一个的节点,然后更新节点
1.这里定义全局的head和pre。
2.整体思路按照中序遍历来走,pre如果为空则表示是这棵树左下的节点,那么将其定义为头节点。
3.如果pre不空的话,就表示当前遍历的节点的左子树的右下节点。
4.遍历完成后,pre指向这棵树右下的节点。
5.最后将其首尾连接起来。
作者:xiao-zhu-ssp
链接:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/solution/jian-zhi-36er-cha-sou-suo-shu-bian-shuan-k52m/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
执行用时: 28 ms , 在所有 Python3 提交中击败了 98.83% 的用户 内存消耗: 16.1 MB , 在所有 Python3 提交中击败了 32.83% 的用户
"""
# Definition for a Node.
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
"""
class Solution:
def treeToDoublyList(self, root: 'Node') -> 'Node':
if(not root):
return None
self.head=None
self.pre=self.head
def inOrder(root):
if(root==None):
return
inOrder(root.left)
if(self.head==None):
self.head=root
else:
self.pre.right=root
root.left=self.pre
self.pre=root
inOrder(root.right)
inOrder(root)
self.pre.right=self.head
self.head.left=self.pre
return self.head