题解 | #二叉树的下一个结点#
二叉树的下一个结点
http://www.nowcoder.com/practice/9023a0c988684a53960365b889ceaf5e
【剑指offer】二叉树的下一个结点(python)
分两种情况,一个是当前结点有右子树,一个是当前结点没有右子树。
有右子树:返回该右子树的最左结点,往左遍历即可
没有右子树:向上找父节点,该父节点的左孩子需等于当前结点,当前结点向上遍历。
class Solution:
def GetNext(self, pNode):
# write code here
if pNode.right:
p = pNode.right
while p.left:
p = p.left
return p
while pNode.next:
if pNode.next.left == pNode:
return pNode.next
pNode = pNode.next
return