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

class TreeLinkNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
        self.next = None

# 这题多个了一个子节点指向父节点的指针.
# 考虑一下,中序遍历的下一个节点分这样一些条件:
# 1. 如果该节点没有右孩子节点,则往上找父节点
#     1.1 如果该节点是其父节点的左节点,那么直接返回其父节点
#     1.2 如果该节点是其父节点的右节点,那么当前节点指向父节点,并继续向上找,
#         直到当前节点为其父节点的左节点,返回此时节点的父节点
# 2. 如果该节点存在右节点:
#     2.1 该右节点不再有左孩子节点,则下个节点就是它
#     2.2 该右节点还有左孩子节点,则继续向下找左孩子节点,直至找到的节点不再有左孩子

class Solution:
    def GetNext(self, pNode: TreeLinkNode):
        if not pNode.right:
            tempnode = pNode
            if pNode.next:
                tempnodefu = pNode.next
            else:
                return None
            while tempnode == tempnodefu.right:
                tempnode = tempnodefu
                tempnodefu = tempnodefu.next
                if not tempnodefu:
                    return None
            return tempnodefu
        else:
            tempnode = pNode.right
            while tempnode.left:
                tempnode = tempnode.left
            return tempnode