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

# 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 not pNode:
            return None
        #如果该节点存在右子树，那中序的下一个节点一定是右子树上最左下角的节点
        if pNode.right:
            tmp = pNode.right
            while tmp.left:
                tmp = tmp.left
            return tmp
        #如果该节点不存在右子树，但该节点是父节点的左子节点，那么下一个遍历的就是父节点
        if pNode.next and pNode.next.left == pNode:
            return pNode.next
        #如果该节点不存在右子树，并且该节点是父节点的右子节点，那么需要逐层向上寻找，知道子树的根节点是父节点的左子节点。
        if pNode.next and pNode.next.right == pNode:
            tmp = pNode.next
            while tmp.next and tmp.next.right==tmp:
                tmp = tmp.next
            return tmp.next
        return None