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

一、思路

分两种情况 （1）当前节点有右孩子，那么就去找当前节点右子树最左边的那个孩子节点 （2）当前节点没有右孩子，那么向上找父节点 -若当前节点是其父节点的左孩子，那么直接返回父节点 -若当前节点不是其父节点的左孩子，那么循环向上查找一直到满足当前节点是其父节点的左孩子的情况为止

# 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 not pNode:
            return pNode
        #当前节点有右孩子，那么就去找当前节点右子树最左边的那个孩子节点
        if pNode.right:
            pNode = pNode.right
            while pNode.left:
                pNode = pNode.left
            return pNode
        #当前节点没有右孩子，那么向上找父节点
        while pNode.next:
            root = pNode.next
            if root.left == pNode:
                return root 
            pNode = pNode.next
        return None