Python二叉树的下一个结点
三种情况:当前节点有右子树的话,当前节点的下一个结点是右子树中的最左子节点;当前节点无右子树但是是父节点的左子节点,下一个节点是当前结点的父节点;当前节点无右子树而且是父节点的右子节点,则一直向上遍历,直到找到最靠近的一个祖先节点pNode,pNode是其父节点的左子节点,那么输入节点的下一个结点就是pNode的父节点。
- '''
- 给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。
- 注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。
- '''
- # -*- coding:utf-8 -*-
- class TreeLinkNode:
- def __init__(self, x):
- self.val = x
- self.left = None
- self.right = None
- self.next = None
- class Solution:
- def GetNext(self, pNode):
- if pNode == None:
- return
- pNext = None
- if pNode.right != None:
- pRight = pNode.right
- while pRight.left != None:
- pRight = pRight.left
- pNext= pRight
- elif pNode.next != None:
- pCurrent = pNode
- pParent = pCurrent.next
- while pParent != None and pCurrent == pParent.right:
- pCurrent = pParent
- pParent = pCurrent.next
- pNext = pParent
- return pNext
-
- class Solution2:
- def GetNext(self, pNode):
- # 输入是一个空节点
- if pNode == None:
- return None
- # 注意当前节点是根节点的情况。所以在最开始设定pNext = None, 如果下列情况都不满足, 说明当前结点为根节点, 直接输出None
- pNext = None
- # 如果输入节点有右子树,则下一个结点是当前节点右子树中最左节点
- if pNode.right:
- pNode = pNode.right
- while pNode.left:
- pNode = pNode.left
- pNext = pNode
- else:
- # 如果当前节点有父节点且当前节点是父节点的左子节点, 下一个结点即为父节点
- if pNode.next and pNode.next.left == pNode:
- pNext = pNode.next
- # 如果当前节点有父节点且当前节点是父节点的右子节点, 那么向上遍历
- # 当遍历到当前节点为父节点的左子节点时, 输入节点的下一个结点为当前节点的父节点
- elif pNode.next and pNode.next.right == pNode:
- pNode = pNode.next
- while pNode.next and pNode.next.right == pNode:
- pNode = pNode.next
- # 遍历终止时当前节点有父节点, 说明当前节点是父节点的左子节点, 输入节点的下一个结点为当前节点的父节点
- # 反之终止时当前节点没有父节点, 说明当前节点在位于根节点的右子树, 没有下一个结点
- if pNode.next:
- pNext = pNode.next
- return pNext
解压密码: detechn或detechn.com
免责声明
本站所有资源出自互联网收集整理,本站不参与制作,如果侵犯了您的合法权益,请联系本站我们会及时删除。
本站发布资源来源于互联网,可能存在水印或者引流等信息,请用户自行鉴别,做一个有主见和判断力的用户。
本站资源仅供研究、学习交流之用,若使用商业用途,请购买正版授权,否则产生的一切后果将由下载用户自行承担。