題目描述
給定一個(gè)二叉樹和其中的一個(gè)結(jié)點(diǎn)，請(qǐng)找出中序遍歷順序的下一個(gè)結(jié)點(diǎn)并且返回。注意，樹中的結(jié)點(diǎn)不僅包含左右子結(jié)點(diǎn)娃胆，同時(shí)包含指向父結(jié)點(diǎn)的指針。
思路
這里主要是分情況討論結(jié)點(diǎn)的情況讲衫。
情況1： 結(jié)點(diǎn)有右孩子
找到右子樹里面的最左結(jié)點(diǎn)缕棵，返回
情況2：結(jié)點(diǎn)沒有右孩子，這時(shí)候有2個(gè)細(xì)分情況涉兽。
情況2.1： 結(jié)點(diǎn)是父節(jié)點(diǎn)的左子樹
返回父節(jié)點(diǎn)
情況2.2： 結(jié)點(diǎn)是父節(jié)點(diǎn)的右子樹
向上搜 不停的找結(jié)點(diǎn)的父節(jié)點(diǎn) 直到找到結(jié)點(diǎn)A招驴，A的 父結(jié)點(diǎn) 的 左結(jié)點(diǎn) 是A。
返回A的父節(jié)點(diǎn)
代碼
# class TreeLinkNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# self.next = None
class Solution:
def GetNext(self, pNode):
# write code here
if pNode is None:
return None
#情況1： 結(jié)點(diǎn)有右孩子
#找到右子樹里面的最左結(jié)點(diǎn)枷畏，返回
if pNode.right is not None:
pNode = pNode.right
while pNode.left is not None:
pNode = pNode.left
return pNode
#情況2.1： 結(jié)點(diǎn)是父節(jié)點(diǎn)的左子樹
#返回父節(jié)點(diǎn)
elif pNode.next is not None and pNode.next.left == pNode:
return pNode.next
#情況2.2： 結(jié)點(diǎn)是父節(jié)點(diǎn)的右子樹
# 向上搜 不停的找結(jié)點(diǎn)的父節(jié)點(diǎn) 直到找到結(jié)點(diǎn)A别厘，A的 父結(jié)點(diǎn) 的 左結(jié)點(diǎn) 是A。
# 返回A的父節(jié)點(diǎn)
elif pNode.next is not None and pNode.next.right == pNode:
while pNode.next is not None and pNode.next.left != pNode:
pNode = pNode.next
return pNode.next
return None
