题解 | #二叉树的下一个结点#
二叉树的下一个结点
http://www.nowcoder.com/practice/9023a0c988684a53960365b889ceaf5e
一、思路
分两种情况 （1）当前节点有右孩子，那么就去找当前节点右子树最左边的那个孩子节点 （2）当前节点没有右孩子，那么向上找父节点 -若当前节点是其父节点的左孩子，那么直接返回父节点 -若当前节点不是其父节点的左孩子，那么循环向上查找一直到满足当前节点是其父节点的左孩子的情况为止
# 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 not pNode:
return pNode
#当前节点有右孩子，那么就去找当前节点右子树最左边的那个孩子节点
if pNode.right:
pNode = pNode.right
while pNode.left:
pNode = pNode.left
return pNode
#当前节点没有右孩子，那么向上找父节点
while pNode.next:
root = pNode.next
if root.left == pNode:
return root
pNode = pNode.next
return None
查看19道真题和解析