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

step1:如果给出的节点有右子节点，则下一个节点就是右子节点的最左节点
step2:如果给出的节点五右子节点且是父级节点的左子节点，则下一节点就是其父节点。如果给出的节点五右子节点且父节点的右子节点，则向上寻找父节点，直到找到该节点是父节点的左子节点，则下一个节点就是该父节点。时O(n)，空O(1)
# -*- coding:utf-8 -*-
# class TreeLinkNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#         self.next = None
class Solution:
    def GetNext(self, pNode):
        p = pNode
        if p.right:
            p = p.right
            while (p.left):
                p = p.left
            return p
        else:
            while (p.next):
                if p.next.left == p:
                    return p.next
                p = p.next
            return None