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

二叉树的下一个结点

http://www.nowcoder.com/practice/9023a0c988684a53960365b889ceaf5e

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
全部评论

相关推荐

10-30 23:23
已编辑
中山大学 C++
去B座二楼砸水泥地:这无论是个人素质还是专业素质都👇拉满了吧
点赞 评论 收藏
分享
10-05 23:02
东北大学 Java
我说句实话啊:那时候看三个月培训班视频,随便做个项目背点八股,都能说3 40w是侮辱价
点赞 评论 收藏
分享
2 收藏 评论
分享
牛客网
牛客企业服务