题解 | #二叉树的下一个结点#

# 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.right:
            tmp=pNode.right
            while tmp.left:
                tmp=tmp.left
            return tmp
        else:
            while pNode.next:
                parent=pNode.next
                if parent.left==pNode:
                    return parent
                pNode=pNode.next
        return None