Python二叉搜索树与双向链表
按照左右子树分治,递归实现。根的左边连接左子树的最右边结点,右边连接右子树的最左边结点。
- '''
- 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。
- 要求不能创建任何新的结点,只能调整树中结点指针的指向。
- '''
-
- # -*- coding:utf-8 -*-
- class TreeNode:
- def __init__(self, x):
- self.val = x
- self.left = None
- self.right = None
- class Solution:
- def Convert(self, pRootOfTree):
- if pRootOfTree == None:
- return None
- if not pRootOfTree.left and not pRootOfTree.right:
- return pRootOfTree
-
- # 处理左子树
- self.Convert(pRootOfTree.left)
- left = pRootOfTree.left
-
- # 连接根与左子树最大结点
- if left:
- while left.right:
- left = left.right
- pRootOfTree.left, left.right = left, pRootOfTree
-
- # 处理右子树
- self.Convert(pRootOfTree.right)
- right = pRootOfTree.right
-
- # 连接根与右子树最小结点
- if right:
- while right.left:
- right = right.left
- pRootOfTree.right, right.left = right, pRootOfTree
-
- while pRootOfTree.left:
- pRootOfTree = pRootOfTree.left
-
- return pRootOfTree
-
- pNode1 = TreeNode(8)
- pNode2 = TreeNode(6)
- pNode3 = TreeNode(10)
- pNode4 = TreeNode(5)
- pNode5 = TreeNode(7)
- pNode6 = TreeNode(9)
- pNode7 = TreeNode(11)
-
- pNode1.left = pNode2
- pNode1.right = pNode3
- pNode2.left = pNode4
- pNode2.right = pNode5
- pNode3.left = pNode6
- pNode3.right = pNode7
-
- S = Solution()
- newList = S.Convert(pNode1)
- print(newList.val)
解压密码: detechn或detechn.com
免责声明
本站所有资源出自互联网收集整理,本站不参与制作,如果侵犯了您的合法权益,请联系本站我们会及时删除。
本站发布资源来源于互联网,可能存在水印或者引流等信息,请用户自行鉴别,做一个有主见和判断力的用户。
本站资源仅供研究、学习交流之用,若使用商业用途,请购买正版授权,否则产生的一切后果将由下载用户自行承担。