二叉搜索树与双向链表 剑指offer python版

本文主要是介绍二叉搜索树与双向链表 剑指offer python版，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

题目

题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

一、思路

【思路】
利用树的中序遍历为基础，进行修改。将中序遍历的顺序反过来，先访问右子树，再访问左子树，这样当修改完树中的指针后，当前节点即为链表的头结点。

【边界情况】

• 链表为空

二、代码

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:def __init__(self):self.next_node=Nonedef Convert(self, pRootOfTree):# write code hereif not pRootOfTree:return Noneself.change_link(pRootOfTree)return self.next_nodedef change_link(self,node):if not node: return None# 遍历右子树if node.right:self.change_link(node.right)# 将当前节点的右指针指向后一个节点node.right=self.next_node# 将后一个节点的左指针指向当前节点if self.next_node:self.next_node.left=node# 在访问左子树之前，将【后一个节点】修改为【当前节点】# 因为对于左子树来说，此时当前节点即为他的后一个节点self.next_node=node#遍历左子树if node.left:self.change_link(node.left)

三、总结

一定要要学会利用基础的树遍历算法，好多题目都是基础树算法衍生出来的。

这篇关于二叉搜索树与双向链表 剑指offer python版的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---