二叉树的下一个节点

WechatIMG1.jpeg

def get_next(p_node):
    """
    获取二叉树（p_node）的下一个节点
    """
    # 针对的是 第1中情况
    if p_node.right:
        tmp = p_node.right
        while tmp.left:
            tmp = tmp.left
        return tmp
    # 针对 2、3、4情况    
    else:
        tmp = p_node
        while tmp.next:
            if tmp.next.left == tmp:
                return tmp.next
            tmp = tmp.next
    return None