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

# -*- 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):
        # write code here
        # 用递归分类查找
        # 先判空
        if pNode == None:
            return None
        # 情况1：节点存在右子树，则打印右子树最左边的叶子结点即可
        if  pNode.right:
            pNode = pNode.right
            while pNode.left:
                pNode = pNode.left
            return pNode
        # 情况2：节点不存在右子树
        # 细分两种情况，节点属于父节点的左子树  右子树  两种情况
        # 情况2.1 节点属于父节点的左子树，那直接打印它的父节点即可
        # 情况2,.2 节点属于父节点的右子树，那就寻找其是否存在  上级节点是上上级节点的左子树
        # 这两种可以合并到一起，都属于2.2
        while pNode.next:
            if pNode.next.left == pNode:
                return pNode.next
            pNode = pNode.next
        return None