今日题目(剑指Offer系列)
剑指 Offer 36. 二叉搜索树与双向链表
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。 要求不能创建任何新的节点,只能调整树中节点指针的指向。 为了让您更好地理解问题,以下面的二叉搜索树为例: 我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表,第一个节点的前驱是最后一个节点,最后一个节点的后继是第一个节点。 下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。 特别地,我们希望可以就地完成转换操作。当转化完成以后,树中节点的左指针需要指向前驱,树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
解题思路:
>题目要求将二叉搜索树转化成一个有序链表,然后头尾变成循环链表 >二叉搜索树有个性质就是二叉搜索树的中序遍历就是有序的 >所以本题可以利用该性质,对中序遍历时中间的节点进行操作 >就是用一个pre作为中间节点,保存上次遍历时的节点 >这样就可以在遍历下一个节点时进行建立连接 >pre.right=cur cur.left=pre pre=cur
Python解法:
class Solution: def treeToDoublyList(self, root: 'Node') -> 'Node': def dfs(cur): if not cur: return dfs(cur.left) if self.pre==None: self.head=cur else: self.pre.right=cur cur.left=self.pre self.pre=cur dfs(cur.right) if root==None: return None self.head=None self.pre=None dfs(root) self.head.left=self.pre self.pre.right=self.head return self.head
Java解法:
class Solution { public Node head,pre; public Node treeToDoublyList(Node root) { if(root==null) { return null; } dfs(root); head.left=pre; pre.right=head; return head; } public void dfs(Node cur) { if(cur==null) { return; } dfs(cur.left); if(pre==null) { head=cur; }else { pre.right=cur; } cur.left=pre; pre=cur; dfs(cur.right); } }